{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "hGPg5M7wsOQY"
   },
   "source": [
    "### 凝聚式层次聚类 \n",
    "\n",
    "聚合法开始将每个样本各自分裂到一个类，之后将相距最近的两类合并，建立一个新的类，重复次操作知道满足停止条件，得到层次化的类别。\n",
    "\n",
    "\n",
    "\n",
    "### k均值聚类\n",
    "\n",
    "k均值聚类是基于中心的聚类方法，通过迭代，将样本分到k个类中，使得每个样本与其所属类的中心或均值最近，得到k个平坦的，非层次化的类别，构成对空间的划分。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "qAlQYJ2Srd2_"
   },
   "outputs": [],
   "source": [
    "import math\n",
    "import random\n",
    "import numpy as np\n",
    "from sklearn import datasets,cluster\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "M_XOaWU5xpjI"
   },
   "outputs": [],
   "source": [
    "iris = datasets.load_iris()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 143
    },
    "colab_type": "code",
    "id": "_swSYxCr0RzU",
    "outputId": "88d09d3b-7700-4af5-e3b6-4d7735a3dd75"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
       "       0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\n",
       "       1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,\n",
       "       2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2])"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "gt = iris['target'];gt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "UoIRpftd9Uh2"
   },
   "source": [
    "目标为聚类为3类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 35
    },
    "colab_type": "code",
    "id": "pI6cS2sjy3Sz",
    "outputId": "3d9d01de-31b4-4eea-989c-b0a986a77af5"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(150, 2)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "iris['data'][:,:2].shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "YwIVX5j81348"
   },
   "outputs": [],
   "source": [
    "data = iris['data'][:,:2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "h-wEZbDR03E_"
   },
   "outputs": [],
   "source": [
    "x = data[:,0]\n",
    "y = data[:,1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 269
    },
    "colab_type": "code",
    "id": "bW_lxjVdy4rW",
    "outputId": "ded2fc31-a69a-4e40-b0d4-350b995488ce"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAD8CAYAAAB0IB+mAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAcUUlEQVR4nO3df4wc9Znn8ffHM2MlkARO57klYGxzErsRLOsAI4LPq5Uv41tBYJN/8gcrR3CWTnPY7IlcdhVd1hKJLXn/Ou0igrB3lOxtLAhRLptwWX6sAs6iEFYQjQk/QshJ3IKND/aYsMpwnNEeNs/9MT2+np6eqequb1dXdX1e0sjTVdXVT327/Ljdz7eeUkRgZmajb92wAzAzs3I44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTVEroQv6VVJL0h6VtJcl/WSdJeklyU9L+mq9KGamVkR4z1s+68j4perrLseuLT18wngUOtPMzOriFRf6XwGOBKLngLOl/TRRPs2M7ME8n7CD+AHkgL484iY7Vh/EfBa2+OTrWVvtG8kaQaYATj33HOv/tjHPtZX0GZmTXXs2LFfRsRkP8/Nm/C3R8Trkv4F8KikX0TEj9rWq8tzVvRsaP1DMQswNTUVc3MrygFmZrYGScf7fW6ur3Qi4vXWn28C3wOu6djkJHBx2+ONwOv9BmVmZullJnxJ50r68NLvwO8CP+vY7PvAza3ZOtcCCxHxBmZmVhl5vtL5NeB7kpa2/2ZE/I2kWwEi4jDwMPAp4GXgFLB7MOGamVm/MhN+RPw9sLXL8sNtvwdwW9rQzMwsJV9pa2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDZE74Usak/RTSQ92WbdD0oKkZ1s/d6QN08zMispzE/MltwMvAR9ZZf0TEXFj8ZDMzGwQcn3Cl7QRuAH42mDDMTOzQcn7lc6dwBeB99fYZpuk5yQ9Iuny4qGZmVlKmQlf0o3AmxFxbI3NngE2R8RW4KvAA6vsa0bSnKS5+fn5vgI2M7P+5PmEvx34tKRXgW8Bn5R0b/sGEfF2RLzT+v1hYELShs4dRcRsRExFxNTk5GTx6M3MLLfMhB8RX4qIjRGxBbgJ+GFEfK59G0kXSFLr92ta+31rAPFaQ933wn1suXML6/avY8udW7jvhfuGHZJZ7fQyS2cZSbcCRMRh4LPAHkmngXeBmyIi0oRoTXffC/cx89cznHrvFADHF44z89czAOy6YtcwQzOrFQ0rL09NTcXc3NxQXtvqZcudWzi+cHzF8s3nbebVz79afkBmQyTpWERM9fNcX2lrlXdi4URPy82sOyd8q7xN523qabmZdeeEb5V3cPog50ycs2zZORPncHD64JAiMqsnJ3yrvF1X7GL292bZfN5mhNh83mZmf2/WBVuzHrloa2ZWIy7amplZJid8M7OGcMI3M2sIJ3wrhVsjmA1f360VzPJyawSzavAnfBu4fUf3nU32S069d4p9R/cNKSKzZnLCt4FzawSzanDCt4FzawSzanDCt4EXVN0awawanPAbbqmgenzhOEGcLaimTPpujWBWDW6t0HDuNW9WL26tYH1zQdWsOZzwG84FVbPmcMJvOBdUzZojd8KXNCbpp5Ie7LJOku6S9LKk5yVdlTZMG5RRKqi6fYPZ2npprXA78BLwkS7rrgcubf18AjjU+tNqYNcVu2qZ4Nu5fYNZtlyf8CVtBG4AvrbKJp8BjsSip4DzJX00UYxmmdy+wSxb3q907gS+CLy/yvqLgNfaHp9sLVtG0oykOUlz8/PzPQVqthbPNjLLlpnwJd0IvBkRx9barMuyFRP8I2I2IqYiYmpycrKHMM3W5tlGZtnyfMLfDnxa0qvAt4BPSrq3Y5uTwMVtjzcCryeJ0Cpv70N7GT8wjvaL8QPj7H1ob+kxeLaRWbbMhB8RX4qIjRGxBbgJ+GFEfK5js+8DN7dm61wLLETEG+nDtarZ+9BeDs0d4kycAeBMnOHQ3KHSk/4ozTYyG5SeWitI2gH8UUTcKOlWgIg4LEnA3cB1wClgd0Ss2TfBrRVGw/iB8bPJvt2Yxjh9x+khRGQ22oq0VujpjlcR8TjweOv3w23LA7itnwCs3rol+7WWm9nw+EpbK2RMYz0tN7PhccK3QmaunulpuZkNjxP+iNt5ZCfar7M/O4/sTLr/e264hz1Te85+oh/TGHum9nDPDfckfR23TbAqS3F+lnGOux/+CNt5ZCdHXzm6Yvn0JdM8dvNjQ4ioP51tE2BxyqVn4VgVpDg/e9lHkaKtE/4I0/5u18Mtii8P533vh2/SYlWW4vzsZR++AYqNNLdNsCpLcX6WdY474VvluW2CVVmK87Osc9wJf4RNXzLd0/LVZBWTBl1sctsEq7IU52dZ57gT/gjbfeVu1NHXTojdV+7OvY+lYtLxheMEcbbP/FJSz1qfgtsmWJWlOD/LOsddtB1hZRSTXFA1K5eLttZVGcUkF1TN6sMJf4SVUUxyQdWsPpzw+1TWlZ9FCqZlFJNcULVB8hXWafXULdMWlXXD7KzXyVq/FMu+o/s4sXCCTedt4uD0wZ6LSWvtI8VrmHXjG9On56JtH8oqVLpgak3m87s7F21LVlah0gVTazKf3+k54fehrEKlC6bWZD6/03PC70NZhUoXTK3JfH6nl5nwJX1A0k8kPSfpRUn7u2yzQ9KCpGdbP3cMJtxqKOuquKzX2XXFLrZt3LbsOds2blsWx96H9jJ+YBztF+MHxrveXLyMmRCebWG98hXW6WUWbVs3KD83It6RNAH8GLg9Ip5q22YHrZub533hOhdtq2LvQ3s5NHdoxfKlG5BkrYdyes27n71ZOgMt2said1oPJ1o/9WmmPsJmj82uuTxrPSxOp2xPxACn3jvFvqP7EkVZzmuYWbZc3+FLGpP0LPAm8GhEPN1ls22tr30ekXT5KvuZkTQnaW5+fr5A2AZwJs6suTxrPZQzE8KzLcyqIVfCj4gzEfFxYCNwjaTf7NjkGWBzRGwFvgo8sMp+ZiNiKiKmJicni8RtcPY+sqstz1oP5cyE8GwLs2roaZZORPwKeBy4rmP520tf+0TEw8CEpA2pgqyiFEXIPAXVtcxcPbPm8qz1sDgTYmLdxLL1E+smepoJkXUcdZptUfR9zfN8F7BtWPLM0pmUdH7r9w8CO4FfdGxzQau4i6RrWvt9K3241ZCiB/xSQbX965dDc4d6Tvpr2b5pO+PrlnfPGF83zvZN25cta711qz5eS57jqMtsi6Lva57nl3H/ALPV5Jml81vAN4AxFhP5tyPigKRbASLisKQ/APYAp4F3gS9ExN+ttd86z9JJccn3+IHxrt+xj2mM03ecTrKPPHEWPZYUx1EVRceijPE2KzJLJ7N5WkQ8D1zZZfnhtt/vBu7uJ4A6SlGEzFNQLbqPPHEWPZYUx1EVRceijPE2K8JX2vYhRREyT0G16D7yxFn0WFIcR1UUHYsyxtusCCf8PqQoQuYpqBbdR544ix5LiuOoiqJjUcZ4mxXhhN+HFEXIe264hz1Te5ZNoWy/AjbvPqYvmV62bPqS6bP72HXFLm7Zesuy17hl6y3L4ix6LCmOoyqKjkWe5+dph1GGojPErJ7cD7/GsloWuKVB9eRpd9GEGKx/RYq2Tvg15huk1E8VZjVVIQbrn2+A0lC+QUr9VGFWUxVisOFwwq8x3yClfqowq6kKMdhwNDbhl3EJ/aALYwenD7J+bP2yZevH1vsGKauoQkuDPLOass6boseRd2ZV1usUXZ9HFd6zUZJ54dUo6ixmLl3eDuQqZuZ5fmdhbKnlAJC0MNZZg2l/vBTLvqP7OLFwgk3nbeLg9MFGFmyLvuepLL33s8dmORNnGNMYM1fPnF2edd6kOI6sGCB7vIquz6Mq79koaWTRtoxL6MsojLkom19dxipFu4wUik4ISBFnXd6zsrlo26MyLqEvozDmomx+dRmrFO0yUig6ISBFnHV5z+qkkQm/jEvoyyiMuSibX13GKkW7jBSKTghIEWdd3rM6aWTCL+MS+jJaDrgom19dxipFu4wUsl6n6PoUMVgfImIoP1dffXUM073P3xub/2xz6CuKzX+2Oe59/t6enr/nwT0xtn8s+Aoxtn8s9jy4p+dt8sSQYh+2qC5jNf2N6eArnP2Z/sb0svUpjiPrNfK8zmV3X7ZsH5fdfVnyOOvynpUJmIs+824ji7ZFpWhZkGcfvgS+ecpoh7HzyE6OvnJ0xfLpS6Z57ObHStuH9cetFUpW1gwEXwLfPGXMTNH+1e9oFl/Olw9S7MP641k6JStrBoIvgW8ez0yxQXLC70NZMxB8CXzzeGaKDVKem5h/QNJPJD0n6UVJ+7tsI0l3SXpZ0vOSrhpMuPnkuRy7yCXbqWYgdCbuMY31PNOnCpeep4hh0O0E8rxGntcpo11G1rm188hOtF9nf3Ye2dnTcXTeQ2G15Sn2kaWM9gwp1CXOLHk+4f8T8MmI2Ap8HLhO0rUd21wPXNr6mQFWVhpLslT0Or5wnCDOXo7d/gbk2WYtKW6A8uSJJ1d8NXMmzvDkiSfPPt6+aTvrOt6idaxj+6btSY4jhRQxLBWnl8ZjqZ3AUjIt4zXyvE6efRSVdW51K5YefeXosqSfdRy//s9/vetrty/P2sdjNz/W9eY7vRRss16jCud3neLMo6eiraRzgB8DeyLi6bblfw48HhH3tx7/d2BHRLyx2r4GVbTNU/SqwiXbeQqydeh3nyKGMtoJpBjvKhTR8xRLUxxHGedWHc5vqF6cAy/aShqT9CzwJvBoe7JvuQh4re3xydayzv3MSJqTNDc/P99PvJnyFL2qUBjLU5CtQ7/7FDGU0U4gxXjXpYie4jjKOLfqcH7niaMqceaRK+FHxJmI+DiwEbhG0m92bNLtY8eK/zpExGxETEXE1OTkZO/R5pCn6FWFwliegmwd+t2niKGMdgIpxrsuRfQUx1HGuVWH8ztPHFWJM4+eZulExK+Ax4HrOladBC5ue7wReL1QZH3KU/SqwiXbeQqyZVy+XlSKGMpoJ5BivMtol5ElT7E0xXGUcW7V4fzOE0dV4swl61JcYBI4v/X7B4EngBs7trkBeITFT/rXAj/J2u8gWyukaFlQhjwxZB1LFS49L+NS/xTvV4p2GCnaHhR9T/O0Rcg6jhTnXgpFx6Ks878qcUQMuLWCpN8CvgGMsfg/gm9HxAFJt7b+wTgsScDdLH7yPwXsjog1K7LDvNK2jMvXLb+s96Os96toHHniLONYm3J+N+U4O7m1Qo+qUv23RVWZBVHGTT9845B0mnKcndxaoUd1qqo3QVVmQZRx0w/fOCSdphxnSo1M+HWqqjdBVWZBlHHTD984JJ2mHGdKjUz4taqqN8DB6YNMrJtYtmxi3cSyWRBZbSig+OXteWZjdLvyuX39WseR91jXeo08x5nq/K56u4C8x1nGcVR9rJY0MuGnaI1gaS3W/bs/ztOGIsXl7VnnxZMnnuR93l/2nPd5f1kcax1H3mNd6zXyHGeK87sO7QLyHGcZx1GHsVrSyKKtVUtdWgGkaAFR9FirUsCuiyq0iEjNRVurtbq0AkjRAqLosValgF0XVWgRUSVO+DZ0dWkFkKIFRNFjrUoBuy6q0CKiSpzwbegFp4PTB1k/tn7ZsvVj63tuBbDavnux1likaAFR9FjLmnAwKhMbqtAiokqc8BuuKgWnzlpS++N7briHPVN7zn7KHdPYihu5/8mP/qTrfldb3k3WWGTFkbdYutaxZt0DoawJB6MysaGM46jTWLlo23BVKM6liCHFTbWrUOCrwvth1eairfWtCgWnKsRQVhxVuarYmskJv+GqUHCqQgxlxVGVq4qtmZzwG64KBacUMVy24bKelg8qjqKvUYX3w0aXE37DlVVwWmv2S94rJteaSfTibS9y4YcuXLbswg9dyIu3vZg7xhRxFH2NOhUA7f8b9ky3vFy0tYEr2rc8RZ/5KhyHjaayzwv3w7dKKzrzJEXLghQ8g8a6cWsFszZFZ56kaFmQgmfQWDd1Oi+c8G3gis48SdGyIAXPoLFu6nReZCZ8SRdL+ltJL0l6UdLtXbbZIWlB0rOtnzsGE27zFC0GVaGYlNVOANaOM2+f+WHPsMlr70N7GT8wjvaL8QPj7H1ob7IY86rCeTEq6jSzajzHNqeBP4yIZyR9GDgm6dGI+HnHdk9ExI3pQ2yuzmLQ0qX+QF/Fzl6fn9Ja7QTyxJnVZ35pu31H93Fi4QSbztvEwemDyS+hL/oaex/ay6G5Q2cfn4kzZx+3t4oYpCqdF6OgjHMvlZ6LtpL+G3B3RDzatmwH8Ee9JHwXbbOVUewsQxk3B6+LPL39B22UxrOJSivaStoCXAk83WX1NknPSXpE0uWrPH9G0pykufn5+Z6DbZoyip1lKOPm4HWRp7f/oI3SeFpvcid8SR8C/gr4fES83bH6GWBzRGwFvgo80G0fETEbEVMRMTU5OdlvzI1RRrGzDGXcHLwu8vT2H7RRGk/rTa6EL2mCxWR/X0R8t3N9RLwdEe+0fn8YmJC0IWmkDVS0GFSVYlLRdgJVOY4U8vT2H7RRGk/rTZ5ZOgK+DrwUEX+6yjYXtLZD0jWt/b6VMtAm2nXFLm7Zesuy/uu3bL0ldzGoKpfp77piF9s2blu2bNvGbbnbCVTlOFLI09t/0EZpPK03mUVbSb8NPAG8ALzfWvzHwCaAiDgs6Q+APSzO6HkX+EJE/N1a+3XRNtuoXMrfOTNlSdmJzmwUuLXCiBqV2RRVmJliNircWmFEjcpsiirMTDEzJ/xKG5XZFFWYmWJmTvirqsKl53lmU1QhzixVmJlSJXV4z2w0OeF3sVQsPb5wnCDOXnpe9l/MrNkUVYkzy/ZN21nXcaqtYx3bN20fUkTDU5f3zEaTi7Zd1KVY6jjrx2NhRblom1hdiqWOs348FjZMTvhd1KVY6jjrx2Nhw+SE30VdLj13nPXjsbBhcsLvoi6XnjvO9IrenCRrBk6dxsJGj4u2Zi1FW0CMSisMqzYXbc0SmD0229PyTvuO7luW7AFOvXeKfUf3FY7NLAUnfLOWoi0gPAPHqs4J36ylaAsIz8CxqnPCN2sp2gLCM3Cs6pzwzVqK3pzEM3Cs6jxLx8ysRjxLx8zMMjnhm5k1RJ6bmF8s6W8lvSTpRUm3d9lGku6S9LKk5yVdNZhwrZN7q5tZXuM5tjkN/GFEPCPpw8AxSY9GxM/btrkeuLT18wngUOtPG6DOKzuXeqsDLhSa2QqZn/Aj4o2IeKb1+/8GXgIu6tjsM8CRWPQUcL6kjyaP1pbxlZ1m1ouevsOXtAW4Eni6Y9VFwGttj0+y8h8FJM1ImpM0Nz8/31uktoKv7DSzXuRO+JI+BPwV8PmIeLtzdZenrJjvGRGzETEVEVOTk5O9RWor+MpOM+tFroQvaYLFZH9fRHy3yyYngYvbHm8EXi8enq3FV3aaWS/yzNIR8HXgpYj401U2+z5wc2u2zrXAQkS8kTBO68JXdppZLzKvtJX028ATwAvA+63FfwxsAoiIw61/FO4GrgNOAbsjYs3LaH2lrZlZ74pcaZs5LTMifkz37+jbtwngtn4CMDOzcvhKWzOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4ZwwjczawgnfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4Zwwjcza4g8NzH/C0lvSvrZKut3SFqQ9Gzr5470YZqZWVGZ97QF/pLFG5QfWWObJyLixiQRmZnZQGR+wo+IHwH/WEIsZmY2QKm+w98m6TlJj0i6PNE+zcwsoTxf6WR5BtgcEe9I+hTwAHBptw0lzQAzAJs2bUrw0mZmllfhT/gR8XZEvNP6/WFgQtKGVbadjYipiJianJws+tJmZtaDwglf0gWS1Pr9mtY+3yq6XzMzSyvzKx1J9wM7gA2STgJfBiYAIuIw8Flgj6TTwLvATRERA4vYzMz6kpnwI+L3M9bfzeK0TTMzqzBfaWtm1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hCZCV/SX0h6U9LPVlkvSXdJelnS85KuSh+mmZkVlecT/l8C162x/nrg0tbPDHCoeFhmZpZaZsKPiB8B/7jGJp8BjsSip4DzJX00VYBmZpbGeIJ9XAS81vb4ZGvZG50bSpph8X8BAP+02tdEFbMB+OWwg8jBcaZVhzjrECM4ztR+o98npkj46rIsum0YEbPALICkuYiYSvD6A+U403Kc6dQhRnCcqUma6/e5KWbpnAQubnu8EXg9wX7NzCyhFAn/+8DNrdk61wILEbHi6xwzMxuuzK90JN0P7AA2SDoJfBmYAIiIw8DDwKeAl4FTwO6crz3bR7zD4DjTcpzp1CFGcJyp9R2nIrp+3W5mZiPGV9qamTWEE76ZWUOUkvAljUn6qaQHu6yrRGuGjBh3SFqQ9Gzr545hxNiK5VVJL7TiWDE9q0LjmRXn0MdU0vmSviPpF5JekrStY31VxjIrziqM5W+0vf6zkt6W9PmObYY+njnjHPp4tuL4j5JelPQzSfdL+kDH+t7HMyIG/gN8Afgm8GCXdZ8CHmFxPv+1wNNlxNRjjDu6LR9SnK8CG9ZYX5XxzIpz6GMKfAP4d63f1wPnV3Qss+Ic+lh2xDMG/AOwuYrjmSPOoY8nixevvgJ8sPX428C/LTqeA/+EL2kjcAPwtVU2GXprhhwx1snQx7MOJH0E+B3g6wAR8X8j4lcdmw19LHPGWTXTwP+IiOMdy4c+nh1Wi7MqxoEPShoHzmHl9U09j2cZX+ncCXwReH+V9au1ZihTVowA2yQ9J+kRSZeXFFc3AfxA0jEttqroVIXxhOw4Ybhj+i+BeeC/tL7K+5qkczu2qcJY5okTqnN+AtwE3N9leRXGs91qccKQxzMi/ifwn4ETLLapWYiIH3Rs1vN4DjThS7oReDMijq21WZdlpc0VzRnjMyz+t28r8FXggVKC6257RFzFYpfS2yT9Tsf6oY5nm6w4hz2m48BVwKGIuBL4P8B/6timCmOZJ85hj+VZktYDnwb+a7fVXZYNZV54RpxDH09J/4zFT/CXABcC50r6XOdmXZ665ngO+hP+duDTkl4FvgV8UtK9HdsMuzVDZowR8XZEvNP6/WFgQtKGEmNsj+X11p9vAt8DrunYZNjjCWTHWYExPQmcjIinW4+/w2Ji7dxm2GOZGWcFxrLd9cAzEfG/uqyrwnguWTXOioznTuCViJiPiPeA7wL/qmObnsdzoAk/Ir4UERsjYguL/336YUR0/is11NYMeWKUdIEktX6/hsVxe6usGNviOFfSh5d+B34X6Ow4OvRWF3niHPaYRsQ/AK9JWuo8OA38vGOzoY9lnjiHPZYdfp/VvyYZ+ni2WTXOioznCeBaSee0YpkGXurYpufxTNEts2eSboXCrRkGqiPGzwJ7JJ0G3gVuilaZvGS/BnyvdS6OA9+MiL+p4HjmibMKY/ofgPta/73/e2B3BccyT5xVGEsknQP8G+Dfty2r3HjmiHPo4xkRT0v6DotfL50GfgrMFh1Pt1YwM2sIX2lrZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQ/w/olI6JG1P6eQAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.scatter(x, y, color='green')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "WkcMa9cs2onL"
   },
   "outputs": [],
   "source": [
    "# 定义聚类数的节点\n",
    "\n",
    "class ClusterNode:\n",
    "    def __init__(self, vec, left=None, right=None, distance=-1, id=None, count=1):\n",
    "        \"\"\"\n",
    "        :param vec: 保存两个数据聚类后形成新的中心\n",
    "        :param left: 左节点\n",
    "        :param right:  右节点\n",
    "        :param distance: 两个节点的距离\n",
    "        :param id: 用来标记哪些节点是计算过的\n",
    "        :param count: 这个节点的叶子节点个数\n",
    "        \"\"\"\n",
    "        self.vec = vec\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "        self.distance = distance\n",
    "        self.id = id\n",
    "        self.count = count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "_M1vGW8s5ycx"
   },
   "outputs": [],
   "source": [
    "def euler_distance(point1: np.ndarray, point2: list) -> float:\n",
    "    \"\"\"\n",
    "    计算两点之间的欧氏距离，支持多维\n",
    "    \"\"\"\n",
    "    distance = 0.0\n",
    "    for a, b in zip(point1, point2):\n",
    "        distance += math.pow(a - b, 2)\n",
    "    return math.sqrt(distance)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "udgrrhsn19X1"
   },
   "outputs": [],
   "source": [
    "# 层次聚类（凝聚式）\n",
    "\n",
    "class Hierarchical:\n",
    "    def __init__(self, k):\n",
    "        self.k = k\n",
    "        self.labels = None\n",
    "        \n",
    "    def fit(self, x):\n",
    "        nodes = [ClusterNode(vec=v, id=i) for i, v in enumerate(x)]\n",
    "        distances = {}\n",
    "        point_num, feature_num = x.shape\n",
    "        self.labels = [-1] * point_num\n",
    "        currentclustid = -1\n",
    "        while(len(nodes)) > self.k:\n",
    "            min_dist = math.inf\n",
    "            nodes_len = len(nodes)\n",
    "            closest_part = None\n",
    "            for i in range(nodes_len - 1):\n",
    "                for j in range(i+1, nodes_len):\n",
    "                    d_key = (nodes[i].id, nodes[j].id)\n",
    "                    if d_key not in distances:\n",
    "                        distances[d_key] = euler_distance(nodes[i].vec, nodes[j].vec)\n",
    "                    d = distances[d_key]\n",
    "                    if d < min_dist:\n",
    "                        min_dist = d\n",
    "                        closest_part = (i, j)\n",
    "                        \n",
    "            part1, part2 = closest_part\n",
    "            node1, node2 = nodes[part1], nodes[part2]\n",
    "            \n",
    "            #以下为聚类代表坐标计算，类合并时计算新的代表坐标，此处使用物理质心距离，可根据需要进行修改\n",
    "            new_vec = [ (node1.vec[i] * node1.count + node2.vec[i] * node2.count ) / (node1.count + node2.count)\n",
    "                        for i in range(feature_num)]\n",
    "            \n",
    "            new_node = ClusterNode(vec=new_vec,\n",
    "                                   left=node1,\n",
    "                                   right=node2,\n",
    "                                   distance=min_dist,\n",
    "                                   id=currentclustid,\n",
    "                                   count=node1.count + node2.count)\n",
    "            currentclustid -= 1\n",
    "            del nodes[part2], nodes[part1]\n",
    "            nodes.append(new_node)\n",
    "            \n",
    "        self.nodes = nodes\n",
    "        self.calc_label()\n",
    "        \n",
    "    def calc_label(self):\n",
    "        \"\"\"\n",
    "        调取聚类的结果\n",
    "        \"\"\"\n",
    "        for i, node in enumerate(self.nodes):\n",
    "            # 将节点的所有叶子节点都分类\n",
    "            self.leaf_traversal(node, i)\n",
    "\n",
    "    def leaf_traversal(self, node: ClusterNode, label):\n",
    "        \"\"\"\n",
    "        递归遍历叶子节点\n",
    "        \"\"\"\n",
    "        if node.left == None and node.right == None:\n",
    "            self.labels[node.id] = label\n",
    "        if node.left:\n",
    "            self.leaf_traversal(node.left, label)\n",
    "        if node.right:\n",
    "            self.leaf_traversal(node.right, label)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 107
    },
    "colab_type": "code",
    "id": "LwD9Iots6871",
    "outputId": "be527c5e-3be7-40ee-c361-37a0ab57440b"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2\n",
      " 2 2 2 2 2 2 2 2 2 2 2 2 2 0 0 0 0 0 0 0 2 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 2 0 0 0 1 0 0 1 2 1 0 1 0\n",
      " 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0\n",
      " 0 0]\n"
     ]
    }
   ],
   "source": [
    "my = Hierarchical(3)\n",
    "my.fit(data)\n",
    "labels = np.array(my.labels)\n",
    "print(labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "yJN0NPWn8F6K",
    "outputId": "f8238840-dd5e-45b3-e5b2-b4fa3836f7bb"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3df5Acd3nn8fdHu+szaxsriTcxtqxVOCiInfDD3jNWlAMlUhL8A5y74hITcfwKUbyCBC5wXIiuHNuJSO6KCw74LLEHBFwSBpIAMcZOQQBjbII52fgHxuTKCV5Z2MTCxDJGDkHyc390rzQ7mpnu2e7p6dn+vKqmdqb7O91Pf2f22dl+vv0dRQRmZrb8rRh2AGZmVg0nfDOzhnDCNzNrCCd8M7OGcMI3M2sIJ3wzs4Zwwh9hku6RtL4GcayRFJLGu6z/fUnvHeQ+ejzv1ZJuLrLvsgz79cp6HfrtK0n3S9pYTnRWBSf8mur0y9T+CxkRZ0TEjZUH16eIeHtEvG7YcRSR/rF5RpFtDPv1an0dlvoHtGySdkp6SNJjkv6fpJF+n9SdE34DLeWXXNLYIGJpgmEn1Zr7Y2BNRDwVeCnwR5LOGnJMy5YT/ghr/S9A0gpJvyfpHyQ9Iumjkn40Xbfwae43JO0BPpcu/wtJ35a0X9JNks5o2fYHJG2XdL2k7wM/L+kpkv6XpPn0OTdLekpLSJsk7ZH0HUlbW7Z1qaSdLY9/TtKXJD0q6QFJr06Xny/pq+mnvQckXdpHX5wm6WOS9qXHf2WHNkd9qpV048KnSknPkPSF9Ni+I+kj6fKb0uZ3Snpc0q+lyy+QdEd6HF+S9Jy21+a/SboL+L6k8bbX69L0Nbpa0vfS0z0zLc8/M+2L76Wv00ck/VGXY59fSJKSXpEe4+np49dJ+kSH12HhmB5Nj2lty/beIemfJX1T0rk5+//ZafuL8rRfEBH3RMQPFh6mt3/bzzYsPyf85eN3gF8BXgScAvwz8L/b2rwI+Cngl9PHNwDPBH4cuB3Y1db+14FtwAnAzcA7gLOAnwV+FHgr8GRL+58DngVsAC6R9FPtQUpane733cAU8DzgjnT194FXAiuB84FZSb+SdeDpfx/XAfPAGuBU4MNZz+vgD4FPAz8CrEpjJCJemK5/bkQcHxEfkXQm8H7gt4AfA94DXCvp37Rs7+XpcayMiIMd9vfSNM6VwLXAlenxHAN8HPgAST9fA/yHHnF/AVif3n8h8I8kr/XC4y90eM7CMa1Mj+nv0scvAP4eOAn4n8D7JKnHvkn74tPAb0fEh9Nl16V/CDvdrmt7/lWSDgDfAB4Cru+1PysgInyr4Q24H3gceLTldgC4ua3NxvT+vcCGlnVPA34IjJMkwQCe3mN/K9M2J6aPPwBc3bJ+BfAESdJrf+7C9le1LPsKcFF6/1JgZ3r/bcDHc/bBFcA72/Yx3qHdWmBfl3WvXuizTtsAbgRel96/GphrPY6WdgE8o+XxduAP29r8PfCiltfmtR1e04XX61Lgb1vWnQ48kd5/IfAtQC3rbwb+qEs//QZwbcv74HXAh9PH88CZHV6HTn3xauC+lseTaZuTe7xHLwP2Aj9f8P0+RvKB4b8DE8P83VvON3/Cr7dfiYiVCzdgS4+208DHFz5FkfziHwJ+oqXNAwt3JI1J+pP0FNBjJL+8kHyyO6p9uvxY4B96xPDtlvsHgOM7tDmt2zYkvUDS59PTMvuBi9vi6eY0YD46f4rux1sBAV9JT7G8tkfbaeDNrZ9c0zhOaWnzQOenHtbeX8emp5tOAb4VaSbMsa0vAP9e0skkifMjwDpJa4ATOfIfVB6HY4qIA+ndTq/jgouBL0XE5/vYx1Ei4lBE3Ezyn9VskW1Zd074y8cDwLmtfyAi4tiI+FZLm9YE8uvAhcBGkqSwJl2uLu2/A/wLxc+vPtBjGx8iObVxWkScCOxoi6fXNlcruzj6/fTnZMuykxfuRMS3I+I3I+IUklM1V6n7yJwHgG1t/T0ZEde0tFnqVLQPAae2nUo5rVvjiLiP5A/G7wA3RcT3SBL3ZpL/bp7s9LQlxtbuYpK+f2frQkk3pLWBTrcbemxvHJ/DHxgn/OVjB7BN0jSApClJF/ZofwLwA+ARkgT49l4bT5PG+4E/lXRK+h/C2rZz1nnsAjZK+tW0kPljkp7XEtN3I+JfJJ1N8kcpj6+QJMk/kXScpGMlretwDPtITpW8Io3/tbQkF0n/SdKq9OE/kyTFQ+njfwKe3rK5/wNcnP5XonS/50s6IWfMvfxdut83pH10IXB2xnO+ALyBI+frb2x73G4fSf3l6V3W5/U94MXACyX9ycLCiDg3ktpAp9u5AJJ+XNJFko5PX49fJql7fK5gTNaFE/7y8Wckn44/Lel7wJdJCnDdXE1yfvdbwNfT9lneAtwN/F/gu8D/oM/3UETsAc4D3pxu4w7guenqLcDlafyXAB/Nuc1DwEuAZwB7SM4p/1qX5r8J/FeSP3RnAF9qWffvgFslPU7Sl2+MiG+m6y4FPpievvnViNidbutKkj8O95GcAy8sIv4V+I8k5+YfBV5BUpT+QY+nfYHkD+ZNXR637+MASUH+lvSYzikQ76PALwLnSvrDfp5KcvpmL0kfvgN4U0T89VJjsd60+DShmdWRpFuBHRHx58OOxUaXP+Gb1ZCkF0k6OT2l8yrgOcDfDDsuG225rgCUdD/JubpDwMGImGlbL5JTCueRFI9eHRG3lxuqWaM8i+SU1vEko5peFhEPDTckG3W5TumkCX8mIr7TZf15wG+TJPwXAH8WEb3OH5uZWcXKOqVzIclFOhERXwZWSnpaSds2M7MS5J3UKUhGfwTwnoiYa1t/KosvDNmbLlv0L6ikzSRjgznuuOPOevazn72koM3Mmuq22277TkRMLeW5eRP+uoh4UNKPA5+R9I2IaB3u1enimKPOFaV/KOYAZmZmYvfu3X0HbGbWZJLml/rcXKd0IuLB9OfDJJM6tV8EspfFVwKuAh5calBmZla+zISfXkF4wsJ94JeAr7U1uxZ4ZXrF4TnAfo8oMDOrlzyndH6CZFKuhfYfioi/kXQxQETsIJnO9DySqw0PAK8ZTLhmZrZUmQk/Iv6RI5e+ty7f0XI/gNeXG5qZmZXJV9qamTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlDOOGbmTWEE76ZWUM44ZuZNYQTvplZQzjhm5k1hBO+mVlD5E74ksYkfVXSdR3WrZe0X9Id6e2ScsM0M7Oi8nyJ+YI3AvcCT+2y/osRcUHxkMzMbBByfcKXtAo4H3jvYMMxM7NByXtK5wrgrcCTPdqslXSnpBsknVE8NDMzK1Nmwpd0AfBwRNzWo9ntwHREPBd4N/CJLtvaLGm3pN379u1bUsBmZrY0eT7hrwNeKul+4MPAL0ja2dogIh6LiMfT+9cDE5JOat9QRMxFxExEzExNTRWP3szMcstM+BHxtohYFRFrgIuAz0XEK1rbSDpZktL7Z6fbfWQA8VpD7doFa9bAihXJz127hh2R2ejpZ5TOIpIuBoiIHcDLgFlJB4EngIsiIsoJ0Zpu1y7YvBkOHEgez88njwE2bRpeXGajRsPKyzMzM7F79+6h7NtGy5o1SZJvNz0N999fdTRmwyXptoiYWcpzfaWt1d6ePf0tN7POnPCt9lav7m+5mXXmhG+1t20bTE4uXjY5mSw3s/yc8K32Nm2CubnknL2U/Jybc8HWrF9LHqVjVqVNm5zgzYryJ3wzs4ZwwjczawgnfDOzhnDCt0p4agSz4XPR1gbOUyOY1YM/4dvAbd16JNkvOHAgWW5m1XHCt4Hz1Ahm9eCEbwPnqRHM6sEJ3wZeUPXUCGb14ITfcAsF1fl5iDhSUC0z6XtqBLN68Hz4Dee55s1Gi+fDtyVzQdWsOZzwG84FVbPmcMJvOBdUzZojd8KXNCbpq5Ku67BOkt4l6T5Jd0k6s9wwbVCWU0HV0zeY9dbP1ApvBO4Fntph3bnAM9PbC4Dt6U8bActhrnlP32CWLdcnfEmrgPOB93ZpciFwdSS+DKyU9LSSYjTL5OkbzLLlPaVzBfBW4Mku608FHmh5vDddtoikzZJ2S9q9b9++vgI168WjjcyyZSZ8SRcAD0fEbb2adVh21AD/iJiLiJmImJmamuojTLPePNrILFueT/jrgJdKuh/4MPALkna2tdkLnNbyeBXwYCkRWu1t2QLj40nRd3w8eVw1jzYyy5aZ8CPibRGxKiLWABcBn4uIV7Q1uxZ4ZTpa5xxgf0Q8VH64VjdbtsD27XDoUPL40KHkcdVJfzmNNjIblL6mVpC0HnhLRFwg6WKAiNghScCVwIuBA8BrIqLnvAmeWmF5GB8/kuxbjY3BwYPVx2O23BWZWqGvb7yKiBuBG9P7O1qWB/D6pQRgo61Tsu+13MyGx1faWiFjY/0tN7PhccK3QhYubsq73MyGxwl/mdu4MSliLtw2bix3+1ddBbOzRz7Rj40lj6+6qtz9eNoEq7Uy3qBVvMkjYii3s846K2ywNmyISL7WZPFtw4ZhR9afnTsjJicXH8PkZLLcbOjKeIP2sQ1gdywx7/oLUJYxdbocLjWkl31J/CUtVmtlvEH72Ia/AMWWNU+bYLVWxhu0oje5E77VnqdNsFor4w1a0ZvcCX8Z27Chv+XdZNWSBl1r8rQJVmtlvEGrepMv9eR/0ZuLtoO3c2eEtLgOJJVbS6qqoLpzZ8T0dBL/9LQLtlYzZbxBc24DF22tkypqSS6omlXLRVvrqIpakguqZqPDCX8Zq6KW5IKq2ehwwl+iqq78LFIwraKW5IKqDZQvsS7XUk/+F72NctG2ykJl0YJpFbUkF1RtIHyJdUe4aFutqgqVLphao/kN3lGRoq0T/hKsWNF5agIJnuz2Ne8D2E9VcZgNhd/gHXmUTsWqKlS6YGqN5jd46Zzwl6CqQqULptZofoOXL+skP3As8BXgTuAe4LIObdYD+4E70tslWdsd5aJtRHWFyqz9tE+B3D718exsxNhYsm5sLHk8jGNxYdeWxG+co1CgaJsn4Qs4Pr0/AdwKnNPWZj1wXT87HvWEXwezs4uT/cJtIalnrY+oZiCEB1uYladIwu+raCtpErgZmI2IW1uWrwfeEhEX5N3WKBdt62J8vPOXhY+NwcGD2euhmoEQHmxhVp6BF20ljUm6A3gY+Exrsm+xVtKdkm6QdEaX7WyWtFvS7n379i0lXmvRKZm3Ls9aD9VMjeDpF8zqIVfCj4hDEfE8YBVwtqSfbmtyOzAdEc8F3g18ost25iJiJiJmpqamisRtHPke2W7Ls9ZDNQMhPNjCrB76GqUTEY8CNwIvblv+WEQ8nt6/HpiQdFJZQdZRGVd8b9mSnHaRkp9btvT3/M2bey/PWg/JgIeJicXrJyb6GwiRdRyjNNhi1927WHPFGlZctoI1V6xh1939vbB5nl90H2ZLlZnwJU1JWpnefwqwEfhGW5uTpeQbVCWdnW73kfLDrYddu5KkOT+flCDn55PH/ST9LVtg+/bFp1+2b+8/6feybl2SgFuNjyfLW7V/922v78Jtl+c4Nm2CubnknL2U/JybS5bXya67d7H5k5uZ3z9PEMzvn2fzJzfnTsh5nl90H2ZFZBZtJT0H+CAwRpLIPxoRl0u6GCAidkh6AzALHASeAH43Ir7Ua7ujXLQtowiZp6BadBt54ix6LGUcR12suWIN8/uP7ozpE6e5/033l/L8ovswK1K0Hc9qEBF3Ac/vsHxHy/0rgSuXEsAoKqMImaegWnQbeeIseixlHEdd7Nnf+aC7LV/K84vuw6wIX2m7BGUUIfMUVItuI0+cRY+ljOOoi9Undj7obsuX8vyi+zArwgl/CcooQuYpqBbdRp44ix5LGcdRF9s2bGNyYnFnTE5Msm1Dvs7I8/yi+zArZKlXbBW9jfqVtmVc8Z1n2oMsdZhaoYzjqIudd+2M6XdOhy5VTL9zOnbe1V9n5Hn+hg9uCC7l8G3DBzd02NJgzV43G2OXjQWXEmOXjcXsdSP8ojUMng+/mRZGCx04cGTZ5OSRETBZ6616Wz61he27tx+1fHZmlqvOv6oxMdjSeT78hvIXpIye8cvHORRHV7THNMbBS6oZ1lSHGGzpPB9+Q2WNsPGUBvXTKdH2Wr5cY7DhcMIfYf6ClNEzps7Dl7otX64x2HA0NuEXnRohz/OLTp2QZds2OOaYxcuOOcZfkNJNHaY02HxW5+FLrcu3fGoL45ePo8vE+OXjbPnU4jdO0ePIE0Oe/RRdn0sZc5jYEUut9ha9DXOUTtH52fM8P89c9GUcx8TE4u1PTCyOw98fkdh5186Y3Da5aHTM5LbJvkfhlKHXCJnZ62YXxbhwW2hT1nFkjdLJ2k/R9bn4ixQ6wqN0+lO0mJnn+VVMOeCibH6jMqVBVkG1quPI2k/R9fmCWOM3eAcu2vapaDEzz/OrmHLARdn8RmVKg6yCalXHkbWfouvzBeE3eNkamfCLFjPzPL+KKQdclM1vVKY0yCqoVnUcWfspuj5fEH6Dl62RCb9oMTPP86uYcsBF2fxGZUqDrIJqVceRtZ+i6/MF4Td46ZZ68r/obdhTK1QxnUBWmzwxlLENSxSdNqEqWVMvlHEceaZ3yNrP6Veevmgbp195eulx+g1+NFy0rVYZUxbk2cbCl4u0m52Fq3wF/LK08AUpB3545I0xOTHJ3Evm2PQz5cyHsfHqjXz2m589avmGn9zA377ybyvbhi2Np1aoWBmDB+oy0sfqpYpROLqs+1eaxR/kywdlbMOWxqN0KlbG4IG6jPSxehmV0UQ2mpzwl6CMwQN1Gelj9TIqo4lsNOX5EvNjJX1F0p2S7pF0WYc2kvQuSfdJukvSmYMJN588V2MXuWK7jMED27YdnbjHxvof6VOHK8/LuIR+0NMJ5NlHnv3k2UYReUa3bLx6I7pMh28br97Y13Fs+MkNHffdvryMbWTKegPX4Q2eJ466xJklq6oLCDg+vT8B3Aqc09bmPOCGtO05wK1Z2x3UKJ08V2OXccV2GaN8sqZe2LkzYsWKxetXrDiyrzpceV7GJfRVTCeQtY88+8mzjTL0Gt3SPrqm0yibMo4jT58X/iKXrDdwHd7gNYyTqkbpSJoEbgZmI+LWluXvAW6MiGvSx38PrI+Ih7pta1BF2zzF0DpcsZ2nIDsK892XUWSsYjqBPHPAZ+2nDvPI5ymWlnEclUzhMApvcKhdnAMv2koak3QH8DDwmdZknzoVeKDl8d50Wft2NkvaLWn3vn37lhJvpjzF0DpcsZ2nIDsK892XUWSsYjqBPHPAZ+1nVOaRL+M4Kikej8IbPE8cdYkzh1wJPyIORcTzgFXA2ZJ+uq1Jp48dR/3rEBFzETETETNTU1P9R5tDnmJoHa7YzlOQHYX57ssoMlYxnUCeOeCz9jMq88iXcRyVFI9H4Q2eJ466xJlDX6N0IuJR4EbgxW2r9gKntTxeBTxYKLIlylNQrcMV23kKsllx1uE4yriEvorpBPLMAZ+1n7zzyA9SnmJpGcdRyRQOo/AGzxNHXeLMI+skPzAFrEzvPwX4InBBW5vzWVy0/UrWdgc5tUIZUxZUIU8MWcdShyvPq7jUP2v+9jzybCOrTRnTHmS1yVqfp1iadRx5+qKSqSiKvsGr+gWoSxwx4KKtpOcAHwTGSP4j+GhEXC7p4vQPxg5JAq4k+eR/AHhNRPSsyA7zStsypkaw8mRNJ1DFdANlxJEnziqOtar+GrqG/iJ7aoU+1aX4b4lKvkyjgjjyxFnFsY7Kl70U1tBfZE+t0KcRKqo3QiVfplFBHHnirOJYGzM9g3+R+9bIhD9CRfVGqOTLNCqII0+cVRxrY6Zn8C9y3xqZ8EepqN4E2zZsY2LFxKJlEysmFn2ZRvtQwjGNHTVipOj0C3m+1GNF26/MClYsWt/rOPIea6995DnOskbYlDGdxUDl/UWuYtqDEZlaoZEJf9OmpK4zPQ1S8nOZ13lqL6n7d358y55bjrpY6FAc4pY9txx+vFConN8/TxDM759n8yc395WkNv3MJuZeMsf0idMIMX3i9KJC5y17buFJnlz0nCd5clEcvY4j77H22kee48w6jjzK6M+By/OLvFDYnZ9PJj2Yn08el5mQq9hHSRpZtLV6GZWpAMqYAqLosdalgD0yqijsLrepFcwGaVSmAihjCoiix1qXAvbIqKKwO0LFYyd8G7pRmQqgjCkgih5rXQrYI6OKwu4IFY+d8G3o9aZtG7ZxzNgxi5YdM3ZM31MBdNt2P3oVKsuYAqLosVYy5UGF+xm4KkZojNAoECf8hqtLvam9ltT6+Krzr2J2Zvbwp9wxjTE7M8tV5x/5Jve33/T2jtvttryTrEJlVhx5i6W9jnXd6nUdR+msW72ur30UVdV+Bq6KERojNArERduGq8PFimUUCMv4Uu0qCpV1uarYRpeLtrZkdag31aVAWEUcdbmq2JrJCb/h6lBvqkuBsIo46nJVsTWTE37D1aHeVEaB8PSTTu9r+aDiKLqPZVMstVpywm+4qupNvUa/5CkQZl3mf8/r7+GU409ZtOyU40/hntffkzvGMuIouo9lUyxtmmEPdcvJRVsbuKLzs5cxz3wdjsOWqYrn5fd8+FZrRUeelDFlQRk8gsY68tQKZkcUHXlSxpQFZfAIGuuoDkPdcnLCt4ErOvKkjCkLyuARNNZRHYa65ZSZ8CWdJunzku6VdI+kN3Zos17Sfkl3pLdLBhNu8xStBdWhlpQ1nQD0LobmnWd+2CNs8tryqS2MXz6OLhPjl4+z5VNbSosxr9rPdT9K6jDULafxHG0OAm+OiNslnQDcJukzEfH1tnZfjIgLyg+xudprQQvTHkC+WlDR55ep13QC7cXQhSkNgMPF0Kx55hfabf3sVvbs38PqE1ezbcO2UoupZexjy6e2sH339sOPD8Whw49bp4oYpDz9bX1Y+GXaujU5jbN6dZLsl8PUCpL+GrgyIj7Tsmw98JZ+Er6LttmK1oLqMG0CVPPl4KMiz9z+g7ac+rOJKivaSloDPB+4tcPqtZLulHSDpDO6PH+zpN2Sdu/bt6/vYJumaC2oLrWkKr4cfFTkmdt/0JZTf1p/cid8SccDfwW8KSIea1t9OzAdEc8F3g18otM2ImIuImYiYmZqamqpMTdG0VpQXWpJVXw5+KjIM7f/oC2n/rT+5Er4kiZIkv2uiPhY+/qIeCwiHk/vXw9MSDqp1EgbqGgtqC61pKLTCSyn6QbyzO0/aMupP60/eUbpCHgfcG9E/GmXNien7ZB0drrdR8oMtIk2bYJXvQrG0g9/Y2PJ47y1oLpM073pZzaxdtXaRcvWrlqbezqB5TTdQJ65/QdtOfWn9SezaCvp54AvAncDT6aLfx9YDRAROyS9AZglGdHzBPC7EfGlXtt10TZbxVdsD0z7yJQFVSc6s+XAUyssU3UZZVNUHUammC0XnlphmarLKJui6jAyxcyc8GutLqNsiqrDyBQzc8LvqhZTEuQYZVOHOLPUYWRKnXhaAxsWJ/wOFoql8/MQcWRKgqqTadYom7rEmWXd6nWsaHurrWAF61avG1JEw7MwrcH8/nmCODytgZO+VcFF2w5GpVg6MnH6Uv7D3BdWlIu2JRuVYunIxOlL+Q9zX9gwOeF3MCrF0pGJ05fyH+a+sGFywu+gLlMSZBmZOH0p/2HuCxsmJ/wO6jIlQZaRiXOELuUv+uUkWSNwRqkvbPlx0dYsVXQKiPYvFoHk07sTupXJRVuzEszdNtfX8nZbP7t1UbIHOPDDA2z97NbCsZmVwQnfLFV0CgiPwLG6c8I3SxWdAsIjcKzunPDNUkWngPAIHKs7J3yzVNEvJ/EIHKs7j9IxMxshHqVjZmaZnPDNzBoiz5eYnybp85LulXSPpDd2aCNJ75J0n6S7JJ05mHCt3SjMh29m9TCeo81B4M0RcbukE4DbJH0mIr7e0uZc4Jnp7QXA9vSnDVD7l5wvzIcP9ZtewcyGL/MTfkQ8FBG3p/e/B9wLnNrW7ELg6kh8GVgp6WmlR2uLbN16JNkvOHAgWW5m1q6vc/iS1gDPB25tW3Uq8EDL470c/UcBSZsl7Za0e9++ff1FakcZlfnwzawecid8SccDfwW8KSIea1/d4SlHjfeMiLmImImImampqf4itaOMynz4ZlYPuRK+pAmSZL8rIj7Wocle4LSWx6uAB4uHZ72Mynz4ZlYPeUbpCHgfcG9E/GmXZtcCr0xH65wD7I+Ih0qM0zoYlfnwzawe8ozSWQf8Z+BuSXeky34fWA0QETuA64HzgPuAA8Bryg/VOtm0yQnezPLJTPgRcTOdz9G3tgng9WUFZWZm5fOVtmZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hBO+GZmDeGEb2bWEE74ZmYN4YRvZtYQTvhmZg3hhG9m1hB5vsT8/ZIelvS1LuvXS9ov6Y70dkn5YZqZWVF5vsT8A8CVwNU92nwxIi4oJSIzMxuIzE/4EXET8N0KYjEzswEq6xz+Wkl3SrpB0hklbdPMzEqU55ROltuB6Yh4XNJ5wCeAZ3ZqKGkzsBlg9erVJezazMzyKvwJPyIei4jH0/vXAxOSTurSdi4iZiJiZmpqquiuzcysD4UTvqSTJSm9f3a6zUeKbtfMzMqVeUpH0jXAeuAkSXuBPwAmACJiB/AyYFbSQeAJ4KKIiIFFbGZmS5KZ8CPi5RnrryQZtmlmZjXmK23NzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBoiM+FLer+khyV9rct6SXqXpPsk3SXpzPLDNDOzovJ8wv8A8OIe688FnpneNgPbi4dlZmZly0z4EXET8N0eTS4Ero7El4GVkp5WVoBmZlaO8RK2cSrwQMvjvemyh9obStpM8l8AwA+6ncvfPXAAAAQwSURBVCaqmZOA7ww7iBwcZ7lGIc5RiBEcZ9metdQnlpHw1WFZdGoYEXPAHICk3RExU8L+B8pxlstxlmcUYgTHWTZJu5f63DJG6ewFTmt5vAp4sITtmplZicpI+NcCr0xH65wD7I+Io07nmJnZcGWe0pF0DbAeOEnSXuAPgAmAiNgBXA+cB9wHHABek3Pfc0uIdxgcZ7kcZ3lGIUZwnGVbcpyK6Hi63czMlhlfaWtm1hBO+GZmDVFJwpc0Jumrkq7rsK4WUzNkxLhe0n5Jd6S3S4YRYxrL/ZLuTuM4anhWjfozK86h96mklZL+UtI3JN0raW3b+rr0ZVacdejLZ7Xs/w5Jj0l6U1ubofdnzjiH3p9pHP9F0j2SvibpGknHtq3vvz8jYuA34HeBDwHXdVh3HnADyXj+c4Bbq4ipzxjXd1o+pDjvB07qsb4u/ZkV59D7FPgg8Lr0/jHAypr2ZVacQ+/LtnjGgG8D03XszxxxDr0/SS5e/SbwlPTxR4FXF+3PgX/Cl7QKOB94b5cmQ5+aIUeMo2To/TkKJD0VeCHwPoCI+NeIeLSt2dD7MmecdbMB+IeImG9bPvT+bNMtzroYB54iaRyY5Ojrm/ruzypO6VwBvBV4ssv6blMzVCkrRoC1ku6UdIOkMyqKq5MAPi3pNiVTVbSrQ39Cdpww3D59OrAP+PP0VN57JR3X1qYOfZknTqjP+xPgIuCaDsvr0J+tusUJQ+7PiPgW8A5gD8k0Nfsj4tNtzfruz4EmfEkXAA9HxG29mnVYVtlY0Zwx3k7yb99zgXcDn6gkuM7WRcSZJLOUvl7SC9vWD7U/W2TFOew+HQfOBLZHxPOB7wO/19amDn2ZJ85h9+Vhko4BXgr8RafVHZYNZVx4RpxD709JP0LyCf4ngVOA4yS9or1Zh6f27M9Bf8JfB7xU0v3Ah4FfkLSzrc2wp2bIjDEiHouIx9P71wMTkk6qMMbWWB5Mfz4MfBw4u63JsPsTyI6zBn26F9gbEbemj/+SJLG2txl2X2bGWYO+bHUucHtE/FOHdXXozwVd46xJf24EvhkR+yLih8DHgJ9ta9N3fw404UfE2yJiVUSsIfn36XMR0f5XaqhTM+SJUdLJkpTeP5uk3x6pKsaWOI6TdMLCfeCXgPYZR4c+1UWeOIfdpxHxbeABSQszD24Avt7WbOh9mSfOYfdlm5fT/TTJ0PuzRdc4a9Kfe4BzJE2msWwA7m1r03d/ljFbZt8kXQyFp2YYqLYYXwbMSjoIPAFcFGmZvGI/AXw8fS+OAx+KiL+pYX/mibMOffrbwK703/t/BF5Tw77ME2cd+hJJk8AvAr/Vsqx2/ZkjzqH3Z0TcKukvSU4vHQS+CswV7U9PrWBm1hC+0tbMrCGc8M3MGsIJ38ysIZzwzcwawgnfzKwhnPDNzBrCCd/MrCH+P0Xm6kLlicNgAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result\n",
    "\n",
    "cat1 = data[np.where(labels==0)]\n",
    "cat2 = data[np.where(labels==1)]\n",
    "cat3 = data[np.where(labels==2)]\n",
    "\n",
    "plt.scatter(cat1[:,0], cat1[:,1], color='green')\n",
    "plt.scatter(cat2[:,0], cat2[:,1], color='red')\n",
    "plt.scatter(cat3[:,0], cat3[:,1], color='blue')\n",
    "plt.title('Hierarchical clustering with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "La_XZDI5_Bng"
   },
   "source": [
    "---------------------------------------------------------------------------------------------------------------------------------"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcuDistance(data1, data2):\n",
    "    '''\n",
    "    计算两个模式样本之间的欧式距离\n",
    "    :param data1:\n",
    "    :param data2:\n",
    "    :return:\n",
    "    '''\n",
    "    distance = 0\n",
    "    for i in range(len(data1)):\n",
    "        distance += pow((data1[i]-data2[i]), 2)\n",
    "    return math.sqrt(distance)\n",
    "\n",
    "def maxmin_distance_cluster(data, Theta): \n",
    "    '''    \n",
    "    :param data: 输入样本数据,每行一个特征\n",
    "    :param Theta:阈值，一般设置为0.5，阈值越小聚类中心越多\n",
    "    :return:样本分类，聚类中心\n",
    "    '''    \n",
    "    maxDistance = 0    \n",
    "    start = 0#初始选一个中心点    \n",
    "    index = start#相当于指针指示新中心点的位置\n",
    "    k = 0 #中心点计数，也即是类别 \n",
    "    \n",
    "    dataNum=len(data)\n",
    "    distance=np.zeros((dataNum,))\n",
    "    minDistance=np.zeros((dataNum,))\n",
    "    classes =np.zeros((dataNum,))\n",
    "    centerIndex=[index]     \n",
    "    \n",
    "    # 初始选择第一个为聚类中心点\n",
    "    ptrCen=data[0]    \n",
    "    # 寻找第二个聚类中心，即与第一个聚类中心最大距离的样本点\n",
    "    for i in range(dataNum):\n",
    "        ptr1 =data[i]\n",
    "        d=calcuDistance(ptr1,ptrCen)\n",
    "        distance[i] = d\n",
    "        classes[i] = k + 1\n",
    "        if (maxDistance < d):\n",
    "            maxDistance = d\n",
    "            index = i #与第一个聚类中心距离最大的样本\n",
    "            \n",
    "            minDistance=distance.copy()\n",
    "            maxVal = maxDistance\n",
    "            while maxVal > (maxDistance * Theta):\n",
    "                k = k + 1\n",
    "                centerIndex+=[index] #新的聚类中心\n",
    "                for i in range(dataNum):\n",
    "                    ptr1 = data[i]\n",
    "                    ptrCen=data[centerIndex[k]]\n",
    "                    d = calcuDistance(ptr1, ptrCen)\n",
    "                    distance[i] = d\n",
    "                    #按照当前最近临方式分类，哪个近就分哪个类别 \n",
    "                    if minDistance[i] > distance[i]:\n",
    "                        minDistance[i] = distance[i]\n",
    "                        classes[i] = k + 1\n",
    "                        # 寻找minDistance中的最大距离，若maxVal > (maxDistance * Theta)，则说明存在下一个聚类中心\n",
    "                        index=np.argmax(minDistance)\n",
    "                        maxVal=minDistance[index]\n",
    "                        return classes,centerIndex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calcuDistance(data1, data2):\n",
    "    '''\n",
    "    计算两个模式样本之间的欧式距离\n",
    "    :param data1:\n",
    "    :param data2:\n",
    "    :return:\n",
    "    '''\n",
    "    distance = 0\n",
    "    for i in range(len(data1)):\n",
    "        distance += pow((data1[i]-data2[i]), 2)\n",
    "    return math.sqrt(distance)\n",
    " \n",
    "def maxmin_distance_cluster(data, Theta):\n",
    "    '''\n",
    "    :param data: 输入样本数据,每行一个特征\n",
    "    :param Theta:阈值，一般设置为0.5，阈值越小聚类中心越多\n",
    "    :return:样本分类，聚类中心\n",
    "    '''\n",
    "    maxDistance = 0\n",
    "    start = 0#初始选一个中心点\n",
    "    index = start#相当于指针指示新中心点的位置\n",
    "    k = 0 #中心点计数，也即是类别\n",
    " \n",
    "    dataNum=len(data)\n",
    "    distance=np.zeros((dataNum,))\n",
    "    minDistance=np.zeros((dataNum,))\n",
    "    classes =np.zeros((dataNum,))\n",
    "    centerIndex=[index]\n",
    " \n",
    "    # 初始选择第一个为聚类中心点\n",
    "    ptrCen=data[0]\n",
    "    # 寻找第二个聚类中心，即与第一个聚类中心最大距离的样本点\n",
    "    for i in range(dataNum):\n",
    "        ptr1 =data[i]\n",
    "        d=calcuDistance(ptr1,ptrCen)\n",
    "        distance[i] = d\n",
    "        classes[i] = k + 1\n",
    "        if (maxDistance < d):\n",
    "            maxDistance = d\n",
    "            index = i #与第一个聚类中心距离最大的样本\n",
    " \n",
    "    minDistance=distance.copy()\n",
    "    maxVal = maxDistance\n",
    "    while maxVal > (maxDistance * Theta):\n",
    "        k = k + 1\n",
    "        centerIndex+=[index] #新的聚类中心\n",
    "        for i in range(dataNum):\n",
    "            ptr1 = data[i]\n",
    "            ptrCen=data[centerIndex[k]]\n",
    "            d = calcuDistance(ptr1, ptrCen)\n",
    "            distance[i] = d\n",
    "            #按照当前最近临方式分类，哪个近就分哪个类别\n",
    "            if minDistance[i] > distance[i]:\n",
    "                minDistance[i] = distance[i]\n",
    "                classes[i] = k + 1\n",
    "        # 寻找minDistance中的最大距离，若maxVal > (maxDistance * Theta)，则说明存在下一个聚类中心\n",
    "        index=np.argmax(minDistance)\n",
    "        maxVal=minDistance[index]\n",
    "    return classes,centerIndex\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "fNl9AY6vAFJG"
   },
   "outputs": [],
   "source": [
    "# K-均值算法\n",
    "\n",
    "class MyKmeans:\n",
    "    def __init__(self, n=20):\n",
    "        self.k = 0\n",
    "        self.n = n\n",
    "        \n",
    "    def fit(self, x, centers=None):\n",
    "        # 第一步，调用上述的函数，得到初始选择的中心点\n",
    "        if centers is None:\n",
    "            classes,idx = maxmin_distance_cluster(data,0.6)            \n",
    "            centers = x[idx]\n",
    "            self.k=len(centers)\n",
    "        print(centers)\n",
    "        \n",
    "        inters = 0\n",
    "        while inters < self.n:\n",
    "            #print(inters)\n",
    "            #print(centers)\n",
    "            points_set = {key: [] for key in range(self.k)}\n",
    "\n",
    "            # 第二步，遍历所有点 P，将 P 放入最近的聚类中心的集合中，可在此之前修改x中数据的顺序\n",
    "            for p in x:\n",
    "                nearest_index = np.argmin(np.sum((centers - p) ** 2, axis=1) ** 0.5)\n",
    "                points_set[nearest_index].append(p)\n",
    "\n",
    "            # 第三步，遍历每一个点集，计算新的聚类中心\n",
    "            for i_k in range(self.k):\n",
    "                centers[i_k] = sum(points_set[i_k])/len(points_set[i_k])\n",
    "                \n",
    "            inters += 1\n",
    "\n",
    "        \n",
    "            \n",
    "        return points_set, centers\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "colab": {},
    "colab_type": "code",
    "id": "SyLthTXfBfnV"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[5.1 3.5]\n",
      " [7.9 3.8]\n",
      " [6.7 2.5]]\n"
     ]
    }
   ],
   "source": [
    "#m = MyKmeans(3)\n",
    "m=MyKmeans()\n",
    "points_set, centers = m.fit(data)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 71
    },
    "colab_type": "code",
    "id": "VE2ryNB-O_Zt",
    "outputId": "55a70e58-fccd-4001-c67c-964ede3a8550"
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[5.00392157, 3.40980392],\n",
       "       [6.82391304, 3.07826087],\n",
       "       [5.8       , 2.7       ]])"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "centers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "M26gflVYDzY4",
    "outputId": "abb1b7b1-df4f-4fa1-9a24-1dc722112c2c"
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXwAAAEICAYAAABcVE8dAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjMsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+AADFEAAAgAElEQVR4nO3df5xddX3n8dd7ZqKQhJBA0vJjSKKi2IQVhVl+CKupQQuB1WLdXayW6q5NSfAHagtUHkIVFZbdKqKSNIsKNKjbolhKwdVVQWILGn4KYrtoEzJmkIAQCCBkks/+cc4kN3funXPu3HN/zXk/H4/7yL3nfM+5n3Pm5jNnvt/v+VxFBGZmNvX1dToAMzNrDyd8M7OScMI3MysJJ3wzs5JwwjczKwknfDOzknDCt54j6URJGzodB4Ckb0t6Rwff/48l3TzB+obOlaR1kt5VRGzWfZzwe5ykDZJOrHh9uqQnJL2+Tvt1kkLS4qrlN6bLT2h1zN1C0rCkJc3sIyLeFBHXFhTSZN7/6og4GUDSQPozXNipeNI4/io9t0+ln8/zOhmP7eaEP4VI+mPgC8ApEXHrBE3/FTijYrvfAo4Cft3aCKcOSX2S/P+ntjXAKyJiFvAfgHdJenOHYzKc8KcMScuBvwJ+LyL+KaP5WuDtFQnrD4HrgO0V++uT9BFJP5f0mKSvSZpTse46SY9IelLSLZJ+p2LbtZIul3SzpKcl/bOkl1Rse7mkRyVtlXSfpEV1jml/SVdJGkn/avl6jTbjrmrT9//L9PlvSbopjfPXkn6QLv8qcBBws6Rtkj6ULj9e0u1p+3skva5iv+skXSTpn4FngPmVXSCS3iPpVkmfSbf/haQ3VWz/srT902lX0CpJV9U59h9Kekv6fEl6jG9KX58kaX3Fe96SbvaD9N8H0mP6g4r9nSNpi6TNks4gB0kHSbpf0tl52o+JiH+JiGfHXgI7gUMb2Ye1hhP+1LACuAhYGhHrc7TfBDwELE1fnwFcU9XmQ8ApwOuAQZIEd3nF+huBlwMHAPcDf1O1/R8CHwX2Ax5O4wM4GTg23XYOcDr1/7L4CvAiYBHw28BncxxbtT8HfgHMS2P9KEBEvB3YDJwcETMj4tOSDgFuAC5M4z4P+Iak/Sv290fAfwVmAcM13u+1wE+A/YHPAF+sWPdV4Ifpuk8A75wg7luBJenz16XH8PqK17X+ghv75bQ4PaaxX5CDwN4kv+DOBFZJmjXBeyPpZel7fCYiLkuX/XX6i6zW466q7c+X9AzJZ+3F6bFbhznhTw1vBG4nSTR5XQOckfbl7x0RP65a/6fARyLilxHxG+Avgf8sqS8idkbEVRHxdMW6oyTNqNj+uohYHxHbgWuBV6fLt5Mky1cCRMRPI+KR6uDS5LsUWBERT0TECxHxg+p2OWwnSXTz031M1NV1BnBDRPyf9Bi/BdwLnFTR5ksR8WBEbI+I0Rr7+HlEfCkidgBXA4OS5kp6KXAE8JcVx/KPE8RyK3sm+IsrXr+e2gm/nt8An0hjvgF4HnjFBO0PB74LnB8Ru35hRcSfRsTsOo8jK3cQEZ8EZpJ0Fa4FnmogXmsRJ/yp4UyS/8BXStLYQklXpn/ab5N0TtU21wG/B5zF+Kt7gPnAP4xdwZH8MgngtyT1S7o07bJ4iuSvBYC5FdtXJvFnSf7zExHfBlYDq4BfSVotaZ8a738I8FhEbM11Buq7BNgIfDftnvrzCdouIOnqerLiuI8l+YUxZlPG+1UfNyTHfhDweEQ8l3NfPwQWS5pHkoCvBl6a/rVxFHBbRhyVHkt/AVXGNXOC9n9E8lfZNxp4j3EicRfJL90Lm9mXFcMJf2p4lORq+D8AV4wtjIj3pH/az4yISys3iIhtwLeB5SRXYNWGgTdWXcXtlV6NnwEsA94A7Mvu/lnV2M84EXFZekV4OEl3zYdqNNsEzM3qekivsp8HplcsPqBi/VMR8cGIWAj8PnCuds9gqi4Vuwn4ctUxz4iI/1H5ljkOsZYRYH9Je1UsO6Re4/Tncw/wQeCe9C+lO4APAz+LiCdqbTbJ2Kp9lOSKfK2k/rGFVRcQ1Y97J9jfAPCygmKzJjjhTxERsZkkAZ8k6TM5NzsXeH1E1LrSXA18StJ82DX4OTbTYh+SJPs4SaL9ZN44JR2dPgZIxgVeAHZUt0tj+r/AFyTNljStcgC1yr3AO9K/PE4Bdk0tlfQf08FSAVvT9xp7v18BL63Yz98Ap0l6Y7qvvST9rqTKK/xJiYifk/yVdKGkFymZ/npKxma3Au9ld/fNLVWvq99jB8nP5KW11jfgBeAPSMZYvqx0cL/qAqL6cQRA+nP6k/Rn1ifpWJIxpu82GZMVwAl/CkmT5BuAt0m6OEf7X0bED+us/jTwLZKukKeBfwL+fbruyyQDnpuBB9J1ec0mGch8EthAcuVb7xfU2KDmv5Ik5/fVafd+4LR0n/+JZOB1zGHA94BtJN0kn42Idem6TwEfS7tvzo6IDel+PgpsIenW+DDF/T95O0l//OMkXRz/m+QXZz23kvxy/UGd17VcCHwlPaa3TjbQiHie5C+iQeB/VXYVZm1K8jP4BclfCVeTfJZWTTYWK478BShmnaFkmuk9EXFRZmOzAvgK36xN0q6sl6RdHcuAU4G/73RcVh4DeRopqcXxNEnf52hEDFWtF8kc6WUkMwDelY7Om9luBwFfJ5njPwz8SUTc19mQrExydemkCX8oIh6rs34ZSf/qMuAYkn7SYwqM08zMmlRUl85bgGvSebe3A7MlHVjQvs3MrAC5unRIRt6/LSmAv46INVXrD2bPm0iG02UjlY2U1HtZDjBjxoyjXvnKV04qaDOzsrrzzjsfi4h5k9k2b8I/PiI2K6mq+B1JP6u6zb3WlK1xfUXpL4o1AENDQ7F+fZ6yL2ZmNkbSxslum6tLJ72ph4h4FLgeOLqqyTB73jU4SDJH28zMukRmwpc0Y6zWSVoc600k1REr3UBSiEvpnXVbI2IEMzPrGnm6dH4buD690W4A+EpEfEvSmQARsRq4iWSGzkMk0zLf3ZpwzcxssjITfkT8gqSsa/Xy1RXPg6TqopmZdSnfaWtmVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiXhhG9mVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiXhhG9mVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiWRO+FL6pd0t6Qba6xbImmrpHvSxwXFhmlmZs3K8yXmYz4APAjMqrP+tog4tfmQzMysFXJd4UsaBE4BrmxtOGZm1ip5u3QuA84Bdk7Q5jhJ90q6WdLi5kMzM7MiZSZ8SacCj0bEnRM0uwtYEBFHAJ8DvllnX8slrZe0fsuWLZMK2MzMJifPFf7xwJslbQC+BrxB0trKBhHxVERsS5/fBEyTNLd6RxGxJiKGImJo3rx5zUdvZma5ZSb8iPiLiBiMiIXA6cD3IuKdlW0kHSBJ6fOj0/0+3oJ4raRWXrKOgf2GkXYysN8wKy9Z1+mQzHpOI7N09iDpTICIWA28DVghaRR4Djg9IqKYEK3sVl6yjlUXvAa2zwBgxxODrLpgDrCOK847obPBmfUQdSovDw0Nxfr16zvy3tZbBvYbZscTg+OW988ZZvTX45ebTWWS7oyIocls6zttrevteOKghpabWW1O+Nb1+udsbmi5mdXmhG9db/k5G2DaM3sunPZMstzMcpv0oK1ZuyQDs+tYc+lCdjxxEP1zNrP8nA0esDVrkAdtzcx6iAdtzcwskxO+mVlJOOGbmZWEE761hUsjmHWeZ+lYy7k0gll38BW+tdyaSxfuSva7bJ+RLDeztnHCt5ZzaQSz7uCEby3n0ghm3cEJ31o+oOrSCGbdwYO2JdeOAVWXRjDrDi6tUHKuNW/WW1xawSbNA6pm5eGEX3IeUDUrDyf8kvOAqll55E74kvol3S3pxhrrJOlySQ9Juk/SkcWGaa1yxXknsOLjd9M/ZxjYSf+cYVZ8/O6eHFB1+QaziTUyS+cDwIPArBrrTgZenj6OAVal/1oPuOK8E7jivLFXg+mjt7h8g1m2XFf4kgaBU4Ar6zR5C3BNJG4HZks6sKAYzTK5fINZtrxdOpcB5wA766w/GNhU8Xo4XbYHScslrZe0fsuWLQ0FajYRzzYyy5aZ8CWdCjwaEXdO1KzGsnET/CNiTUQMRcTQvHnzGgjTbGKebWSWLc8V/vHAmyVtAL4GvEHS2qo2w8AhFa8HAf9PK4nFp9yC+kaRAvWNsviUW9oeg2cbmWXLTPgR8RcRMRgRC4HTge9FxDurmt0AnJHO1jkW2BoRI8WHa91m8Sm38NObXg8xAAhigJ/e9Pq2J/2pNNvIrFUaKq0gaQnwZxFxqqQzASJitSQBnwdOAp4F3h0RE9ZNcGmFqUF9o2myr14xSux0qSazojVTWqGh/5ERcQtwS/p8dcXyAM6aTADW46K/seVm1jG+09aaox2NLTezjnHCt6YsOnkd4ydkRbrczLqJE/4UN2fxj5PZM+ljzuIfF7r/B/5xCYuW3QoaBQI0yqJlt/LAPy4p9H1cNsG62rXXwsKF0NeX/HvttZ3ZR5aI6MjjqKOOCmut2Yt+FLAzICoeO2P2oh91OrSGrLj4tmDatj2PY9q2WHHxbZ0OzSxi7dqI6dNjjw/o9OnJ8hbsA1gfk8y7/gKUKUwK6t0TF1FreXfyl7RYV1u4EDZuHL98wQLYsKHwffgLUGxKc9kE62oPP9zY8lbtIwcnfOt6LptgXW3+/MaWt2ofOTjhT2GzF62n1gyaZHl+WQOmrR5QddkE62qf/CRMn77nsunTk+Xt3Ecek+38b/bhQdvWW3HxbQHbqwZttzc02Jk1YNquAdUVF98W/XM2BeyI/jmbPGBr3WXt2ogFCyKk5N9GBmwb3AcetLVaihjszNqHB1TN2suDtlZTEYOdWfvwgKpZ73DCn8KKGOzM2ocHVM16hxP+JLXrzs9mBkyLGOzM2ocHVK2l2nH3aZlMtvO/2UcvD9q2c6Cy2QHTIgY7s/bhAVVriSLuYJ2C8KBte7VroNIDplZqRdzBOgV50LbN2jVQ6QFTK7U23X1aJk74k9CugUoPmFqptenu0zJxwp+Edg1UesDUSq1dd5+WSVYnP7AX8CPgXuAB4GM12iwBtgL3pI8Lsvbby4O2Ee0bqMx6n90lkHfWLH28aNn3A21P1mt7LFr2/Y4ciwd2bVKKuIN1iqGJQds8CV/AzPT5NOAO4NiqNkuAGxt5415P+N1g0bLv16x3P5bUs9ZHtGfGkevZmxWnmYTf0CwdSdOBdcCKiLijYvkS4M8i4tS8++rlWTrdQn2jEDW+h16jxM6BzPXQnhlHnk1kVpyWz9KR1C/pHuBR4DuVyb7CcZLulXSzpMV19rNc0npJ67ds2TKZeK1S9E+8PGs97Znp49lEZt0hV8KPiB0R8WpgEDha0uFVTe4CFkTEEcDngG/W2c+aiBiKiKF58+Y1E7cBaMfEy7PW056ZPp5NZNYdGpqlExFPArcAJ1UtfyoitqXPbwKmSZpbVJDdqIjSCotPuQX1jSZfMN43yuJTbmlo+9lH/B01690f8XcALDp5Xc31yfLE8nM2QN9v9mzS95uGZvpkHUepZhPlKQXgcgHWKVmd/MA8YHb6fG/gNuDUqjYHwK7xgKOBh8de13v08qBtEYOQeQZUJ7J58+ZgwRdq7oMFX4iRkZEkzr4X9lzf98K40gv0/2bPNv2/yX0seY+jFLN08pQCcLkAaxItnqXzKuBu4D7gftIpl8CZwJnp8/eSTNm8F7gdeG3Wfns54SeJK8Y9+udsyr2PZKrk+H2g7bm2X/He90+4j5Xv+0CuOJs9lmaPY0pZsKDGiSBZ3kgbswk0k/BdS2cSpJ3U7g3bSUS+XjIpSGa8Vgsiai3fbWRkhJcd9js89/QTdfcxfZ/9ePbpxzPjbPZYmjmOKaevL0nf1STYuTN/G7MJuJZOmxUyCJljQLWeiz51CdMXvWHCfey96HfRvsM1V1fG2fSxNHEcU06eUgAuF2Ad5IQ/CUUMQuYZUK1lZGSEq66+mr2GTqP/yJtr7qP/yJvZa+g0tN8FmXE2eyyTPY4pKU8pAJcLsE6abF9Qs49e7sOPKGYQMk/Zg3Hv+973x/7HnBYLzr0xFpx7Y7Dwh3uUVmDhD3et2/+Y02L2q7/S8tIKkzmOKStPKYClS/fsv1+6tN1RRqxYEdHfnw7Y9CevrSfgPvxyGOu73++MzzEwcz8ee/BJnrn592H7jN2Npj3DjJO/ydzfmc2j9/2K577zX2B0z/UrPn43V5x3QvsPwGDlSli1avzyFSvgiivKE4NNWjN9+E74PWTl+z7A3/54EzOX/DcANq5+FWw9ZHzDfTex4Mz76q53SYMOGhiAHTXGN/r7YXS0PDHYpHnQtgQq++532Xpw7cZjy+usd0mDDqqVaCdaPlVjsI5wwu8RYzNzBmbut3vhvr+s3XhseZ31LmnQQf116hvVWz5VY7COKG3Cb7Y0Qp7tmy2dUOkfbvh7Hr/jejb+91N3PdjnXOh/fs+G/c/DPufuXj9QkpIGvWL58uzlK1cm3S5S8u/KlXu2bbY0Q54Y8rxPs+vzcBmKYk12tLfZRydn6TRbGiHP9s2WTsgdR99zVaUTnhtXOmHKlzToNRPNkFmxovaduGNtiirNkDVLJ+t9ml2fh8tQ1IRn6TSm2frsebbPU4u+Wa4zPwVlDaguXAgbN45fv2ABbNhQXBx13md0cJCBTZuy4ygiznYda4/xLJ0GNV9OIHv7dpQcKKLEg3UZTfDZiGhfaYY67xOA8sRRRJwuQ1GTZ+k0qNlyArm2b0PJAdeZn4KyBlTbVZqhzv6GJR555JHsOIqI02UoClfKhN9sOYE827ej5ECp6syXRdaAartKM9R6n2lwy6Ev4tJPXZQdRxFxugxF8Sbb+d/so9OlFdpRTiCrTZ4YitiH9Zis0gt5yjc0+x7p+2w/+ODYAbF9H0W8da/Y/KGZsd+svWNkZCRi0aI997FoUfFxFrGPKYZW1sNv1aPTCb8ZRXwBSrfM9LEu046ZKdXJfoKkf/Z7V8TZx8+MuHDWrsfZx8+MBwcPzr0PK1YzCb+Ug7bNKmJ2TLfM9LEu046ZKVkDw6mRkREWH/YyHviTfg7cZ3fv78jTOzng09tqTkmo3ocVz4O2bVavNEEjJQty7SPqDODVW2697+GHG1veQpd+6iL++FV7Jntg3GvrHf7JTUIRs2O6ZaaPdZkumZkyMjLC1VdfxTnHtPVtrcUyE76kvST9SNK9kh6Q9LEabSTpckkPSbpP0pGtCTefPGUPmimtUMTsmOXnbABt33Ohtjc806fZEhHWZfLMTDnxxKRbZuxx4onj9zNRSYKlS2u/d8XySz91EZ89YCcHfvEZ+NhTcNnT8JMXdq3XSzTukznhvutpR3mGIvRKnFmyOvlJ7h6amT6fBtwBHFvVZhlwc9r2WOCOrP22atA2z2BoUYOuTc/yyRiQXXHxbQHPV7V5ftd7FXEc1oUmmpmSZ8A1a+A3o3zD5s2b4z0vnhY7BqrWTyPirXvtGrx97hDFToidkx2wbUd5hiJ0WZy0a5YOMB24CzimavlfA2+veP0vwIET7atVCT9JwuM/y/1zNjXUptWSqZY1/t9pe+44u+E4rM1qfmjSx5gFC2qvX7AgWT9WQ2fcB6c/IpKZOY+/WLXb7KtxM3Y++L6VkzuWrDiz1rdLl8XZTMLPNUtHUj9wJ3Ao8IWIOLdq/Y3AJRGxLn39XeDciFhf1W45sBxg/vz5R22sNRuhSfnKHnS+JEGe0gtZcXbDcVib5Zlhk1WSYIJ9jGzezOLDXsbjTz9XfxbOhbN2t396J4dfuYMH/uUXHHDAAdnxV2pHeYYidFmcLZ+lExE7IuLVwCBwtKTDq2OotVmN/ayJiKGIGJo3b17j0eaQZzC0K0oS5BiQzYqzK47Duk/WwO8E5RvGZuZo3zrpvmr5gfv0cca/S7YrPM4uGcDumThzaOgyMCKeBG4BTqpaNQxUfpfeINCRrJNnQLUbShLkGZDNirMbjsPaLMeAa+bAb53yDdve+c7dM3OWvjgZsas0LV1e5Zxj4Oqrv5zU2GlEO8ozFKFX4swjq88HmAfMTp/vDdwGnFrV5hT2HLT9UdZ+W3mnbRElC9ohTwxZx+LSClNQVjmBPGURsurd11g/7q7at+6V9NmP9d1XDNhWPybdl591rM2uL0q3xBHN9eHnSfivAu4G7gPuBy5Il58JnJk+F/AF4OfAT4ChrP328hegmLVMB7845CXzDw6SPzsn9XjJ/IObPPgGdcssnjZrJuGXsrSCvzjEupa/OCS/shxnFZdWaFARpRHMWqKI0gpdVJ6hpcpynAUqZcL37BbrWv7ikPzKcpwFKmXC9+yWqWtkZIRDX3Fo4zNGusUnP5nM667U17fnjI+s2/iLmjXS7eUC8h5nO46j28/VmMl2/jf76HQ9fM9umZpWvm9lDMwYiLPef1anQ5mcjLIHuQcqm5010isDonlmz7T6OHqotEIpB21tahoZGeHQVx7KgR8+kEc+/QgP/eyhxu/+7LSBAdhR46a8/n4YHW3fQOVUGRBtx3G0+Vx50NYM+MTFn2Df1+7L3gv2ZtZxs/jExZ/odEiNq5XsK5e3a6ByqgyItuM4euhcOeHblDAyMsJVV1/FrJOSOi+zTprFVVdf1Xt9+ROUPQDaN1A5VQZE23EcPXSunPCtZ8abJjJ2dT9tdlIPYNrsab15lV+n7MGu5e26jb+XygVMpB3H0UvnarKd/80+Oj1oa4leGZubyObNm2P6rOlx2GWHxeFXHb7rcdhlh8WMfWfEyMhIp0PMb+3aiL6+PX8gfX17/kC6pZxAr2jHcfRIaQUP2pbcVBibO+v9Z3H9/7ue/U/ff9y6x7/2OG99xVv5/Gc/34HIJmEq/ECspTxoa5PWQ+NNNVX33Vfrub78Xv+BWFdzwi+5Hhpvqqm6775az/Xl9/oPxLqaE37J9dJ4U7Wsq/sxPXWV38s/EOt6Tvgl9453wJo1SRexlPy7Zk2yvNtlXd2P6amr/F7+gZRZj0x186Ct9aSxu2oP+fghmQkfYPuT2xm+cLg377617nbttcm02Wef3b1s+vSW/aL2oK2VTt6r+zE9dZVvveX88/dM9pC8Pv/8zsQzASd86zl5++6r9VRfvvWOHppZ5YRvPafRq/sxvsq3luilmVVZd2YBhwDfBx4EHgA+UKPNEmArcE/6uCBrv77TNp9myzhPlZslKw0uGGzqu1cHFwx2+hA6byp+MDqlh8oj50n4BwJHps/3Af4VWFTVZglwYyNv7ISfrdkvW58KZROsBfzBKN5ULa0g6e+Bz0fEdyqWLQH+LCJOzbsfz9LJ1uyXrfsufavJH4ye1rZZOpIWAq8B7qix+jhJ90q6WdLiOtsvl7Re0votW7Y0HGzZNPtl6z00lmTt5A9GaeVO+JJmAl8Hzo6Ip6pW3wUsiIgjgM8B36y1j4hYExFDETE0b968ycZcGs1+2XovjSVZG/mDUVq5Er6kaSTJ/tqI+Eb1+oh4KiK2pc9vAqZJmltopCXU7Jet+y59q8kfjNLKTPiSBHwReDAiPl2nzQFpOyQdne738SIDLaMrzjuBpadtgr5RIKBvlKWnbeKK807Itb3v0rea/MEorcxBW0knALcBPwF2pos/AswHiIjVkt4LrABGgeeAD0XEP020Xw/aZmvzHdtm1gOaGbR1LZ0u5skUZlbNtXSmKE+mMLMiOeF3MU+mMLMiOeHXsfKSdQzsN4y0k4H9hll5ybq2x5BnMkWPlOE2sy7ghF/DykvWseqC16R3ufax44lBVl3wmrYn/azJFGODuhs3JvfHb9yYvHbSN7NaPGhbQ7MlDdrFg7pm5eNB24I1W9KgXTyoa2aNcMKvodmSBu3iQV0za4QTfg3NljRoF98hb2aNcMKv4YrzTmDFx++mf84wsJP+OcOs+PjduUsatIvvkDezRnjQ1sysh3jQ1szMMjnhm5mVhBO+mVlJOOGbmZWEE76ZWUk44ZuZlYQTvplZSTjhm5mVRJ4vMT9E0vclPSjpAUkfqNFGki6X9JCk+yQd2ZpwrZrr4ZtZXgM52owCH46IuyTtA9wp6TsR8dOKNicDL08fxwCr0n+thaq/5HysHj64vIKZjZd5hR8RIxFxV/r8aeBB4OCqZm8BronE7cBsSQcWHq3t4fzzdyf7Mc8+myw3M6vWUB++pIXAa4A7qlYdDGyqeD3M+F8KSFouab2k9Vu2bGksUhvH9fDNrBG5E76kmcDXgbMj4qnq1TU2GVeVLSLWRMRQRAzNmzevsUhtHNfDN7NG5Er4kqaRJPtrI+IbNZoMA4dUvB4EuuvbQqYg18M3s0bkmaUj4IvAgxHx6TrNbgDOSGfrHAtsjYiRAuO0GlwP38wakWeWzvHAHwE/kXRPuuwjwHyAiFgN3AQsAx4CngXeXXyoVss73uEEb2b5ZCb8iFhH7T76yjYBnFVUUGZmVjzfaWtmVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiXhhG9mVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiXhhG9mVhJO+GZmJeGEb2ZWEk74ZmYl4YRvZlYSTvhmZiWR50vMvyTpUUn311m/RNJWSfekjwuKD9PMzJqV50vMrwI+D1wzQZvbIuLUQiIyM7OWyLzCj4gfAL9uQyxmZtZCRfXhHyfpXkk3S1pc0D7NzKxAebp0stwFLIiIbZKWAd8EXl6roaTlwHKA+fPnF/DWZmaWV9NX+BHxVERsS5/fBEyTNLdO2zURMRQRQ/PmzWv2rc3MrAFNJ3xJB0hS+vzodJ+PN7tfMzMrVmaXjqSvAkuAuZKGgQuBaQARsRp4G7BC0ijwHHB6RETLIjYzs0nJTPgR8faM9Z8nmbZpZmZdzHfampmVhBO+mVlJOOGbmZWEE76ZWUk44ZuZlYQTvplZSTjhm5mVhBO+mVlJOOGbmZWEE76ZWUk44ZuZlYQTvplZSTjhm5mVhBO+mVlJOOGbmZWEE76ZWUk44ZuZlYQTvqxV2yUAAASiSURBVJlZSTjhm5mVRGbCl/QlSY9Kur/Oekm6XNJDku6TdGTxYZqZWbPyXOFfBZw0wfqTgZenj+XAqubDMjOzomUm/Ij4AfDrCZq8BbgmErcDsyUdWFSAZmZWjIEC9nEwsKni9XC6bKS6oaTlJH8FADxfr5uoy8wFHut0EDk4zmL1Qpy9ECM4zqIdNtkNi0j4qrEsajWMiDXAGgBJ6yNiqID3bynHWSzHWZxeiBEcZ9EkrZ/stkXM0hkGDql4PQhsLmC/ZmZWoCIS/g3AGelsnWOBrRExrjvHzMw6K7NLR9JXgSXAXEnDwIXANICIWA3cBCwDHgKeBd6d873XTCLeTnCcxXKcxemFGMFxFm3ScSqiZne7mZlNMb7T1sysJJzwzcxKoi0JX1K/pLsl3VhjXVeUZsiIcYmkrZLuSR8XdCLGNJYNkn6SxjFuelYXnc+sODt+TiXNlnSdpJ9JelDScVXru+VcZsXZDefysIr3v0fSU5LOrmrT8fOZM86On880jg9KekDS/ZK+KmmvqvWNn8+IaPkD+BDwFeDGGuuWATeTzOc/FrijHTE1GOOSWss7FOcGYO4E67vlfGbF2fFzClwNvCd9/iJgdpeey6w4O34uq+LpBx4BFnTj+cwRZ8fPJ8nNq/8G7J2+/lvgXc2ez5Zf4UsaBE4BrqzTpOOlGXLE2Es6fj57gaRZwOuALwJExAsR8WRVs46fy5xxdpulwM8jYmPV8o6fzyr14uwWA8DekgaA6Yy/v6nh89mOLp3LgHOAnXXW1yvN0E5ZMQIcJ+leSTdLWtymuGoJ4NuS7lRSqqJaN5xPyI4TOntOXwpsAb6cduVdKWlGVZtuOJd54oTu+XwCnA58tcbybjiflerFCR0+nxHxS+B/Ag+TlKnZGhHfrmrW8PlsacKXdCrwaETcOVGzGsvaNlc0Z4x3kfzZdwTwOeCbbQmutuMj4kiSKqVnSXpd1fqOns8KWXF2+pwOAEcCqyLiNcAzwHlVbbrhXOaJs9PnchdJLwLeDPxdrdU1lnVkXnhGnB0/n5LmkFzBvwQ4CJgh6Z3VzWpsOuH5bPUV/vHAmyVtAL4GvEHS2qo2nS7NkBljRDwVEdvS5zcB0yTNbWOMlbFsTv99FLgeOLqqSafPJ5AdZxec02FgOCLuSF9fR5JYq9t0+lxmxtkF57LSycBdEfGrGuu64XyOqRtnl5zPE4F/i4gtEbEd+Abw2qo2DZ/Plib8iPiLiBiMiIUkfz59LyKqf0t1tDRDnhglHSBJ6fOjSc7b4+2KsSKOGZL2GXsOvAmorjja8VIXeeLs9DmNiEeATZLGKg8uBX5a1azj5zJPnJ0+l1XeTv1uko6fzwp14+yS8/kwcKyk6WksS4EHq9o0fD6LqJbZMElnQtOlGVqqKsa3ASskjQLPAadHOkzeZr8NXJ9+FgeAr0TEt7rwfOaJsxvO6fuAa9M/738BvLsLz2WeOLvhXCJpOvBG4E8rlnXd+cwRZ8fPZ0TcIek6ku6lUeBuYE2z59OlFczMSsJ32pqZlYQTvplZSTjhm5mVhBO+mVlJOOGbmZWEE76ZWUk44ZuZlcT/B3XMEf1CGKU4AAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# visualize result\n",
    "\n",
    "cat1 = np.asarray(points_set[0])\n",
    "cat2 = np.asarray(points_set[1])\n",
    "#cat3 = np.asarray(points_set[2])\n",
    "\n",
    "for ix, p in enumerate(centers):\n",
    "    plt.scatter(p[0], p[1], color='C{}'.format(ix), marker='^', edgecolor='black', s=256)\n",
    "        \n",
    "plt.scatter(cat1[:,0], cat1[:,1], color='green')\n",
    "plt.scatter(cat2[:,0], cat2[:,1], color='red')\n",
    "plt.scatter(cat3[:,0], cat3[:,1], color='blue')\n",
    "plt.title('K-Means clustering with k=3')\n",
    "plt.xlim(4, 8)\n",
    "plt.ylim(1, 5)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "u5XVOLGBKC4A"
   },
   "source": [
    "#### 寻找 K 值"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "colab": {
     "base_uri": "https://localhost:8080/",
     "height": 281
    },
    "colab_type": "code",
    "id": "uCe9-EHaJrFz",
    "outputId": "4c2fe667-ee92-4909-c582-6605bd862ecc",
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXoAAAEICAYAAABRSj9aAAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4xLjAsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+17YcXAAAgAElEQVR4nO3deXgd9X3v8fdX+77Y1oJlyXjFWCZgI5slqQmb5SyFpIFgspTkpiGkoTdNentv0uZpWtonTbO1vS1tQkJumw2zJbfchGCcYAgEDJYBg1csL9jyJtmyLMvape/944yUIyHbR5bkOTrn83qe8+jMzG+OvjbmMzO/85vfmLsjIiKJKyXsAkREZGIp6EVEEpyCXkQkwSnoRUQSnIJeRCTBKehFRBKcgl4EMLMPm9mTZ9j+TjNrGMXnPW1mfzQ+1YmMjYJeJh0z22tmN0QtrzKz42Z2zbl+prv/2N1XRH2mm9ncsdYqEg8U9DKpmdkdwL3Ae9z9mbDrEYlHCnqZtMzsTuCbQK27P3+aNs+Y2QeC9+8IztTfHSzfYGavBu8/ZmbPBe9/E+y+yczazOy2qM/7MzNrNLNDZvbxGOtMMbMvmdmbwb4/MLPCYFuWmf3IzI6ZWYuZbTCzsqiadpvZSTPbY2YfPqe/KEl6CnqZrD4N/C1wvbvXnaHdM8A7g/fLgd3ANVHLb7kKcPflwdtL3T3P3R8MlsuBQqAC+ARwr5kVx1Drx4LXtcBsIA/412DbHcFnVgJTgbuADjPLBf438C53zweuBl6N4XeJvIWCXiarG4H1wOtnafcMQ4P976OWr2GEoD+DHuAed+9x98eBNuCiGPb7MPAtd9/t7m3AF4FVZpYWfOZUYK6797n7RndvDfbrBxaZWba7H3L3LaOoVWSQgl4mq7uA+cD3zMzO0O4FYH7QHXIZ8AOg0symAcuA35xh3+GOuXtv1HI7kbPzs5kOvBm1/CaQBpQBPwTWAKvN7KCZfc3M0t39FHAbkT/nITP7hZktGEWtIoMU9DJZNQLXA78H/NvpGrl7O7AR+Cyw2d27geeBzwO73P3oeaj1IDAzarkK6AWOBFcHf+PuC4l0z7wX+MOg9jXufiNwAbAd+O55qFUSkIJeJi13PwhcB6w0s388Q9NngLv5XTfN08OWR3KESH/6eHgA+JyZzTKzPOArwIPu3mtm15rZJWaWCrQS6crpM7MyM7sp6KvvItJN1DdO9UiSUdDLpObu+4mE/S1m9venafYMkM/vummGL4/kr4H/DEbCfHCMZX6fSBfNb4A9QCfwJ8G2cuARIiG/LajtR0T+3/wzIlcDzUS+T/jjMdYhScr04BERkcSmM3oRkQSnoBcRSXAKehGRBKegFxFJcGmxNDKzlcA/A6nA99z9q8O23wV8hsjwrzbgTnffGmz7IpHbxfuA/+7ua870u6ZNm+YXXnjhKP8YIiLJbePGjUfdvWSkbWcddROM732DyC3nDcAG4PaBIA/aFAzctm1mNwF/7O4rzWwhkTHEy4jcHfgrYL67n3Y8cE1NjdfVnWnqEhERGc7MNrp7zUjbYum6WQbUB/N0dAOrgZujG0TNzQGQCwwcPW4GVrt7l7vvAeqDzxMRkfMklq6bCmB/1HIDcMXwRmb2GSK3lWcQuYFlYN/1w/atGGHfO4E7AaqqqmKpW0REYhTLGf1IE0a9pb/H3e919znA/wK+NMp973P3GnevKSkZsYtJRETOUSxB30BkruwBM4jcln06q4H3neO+IiIyzmIJ+g3AvGBCpgxgFfBYdAMzmxe1+B5gZ/D+MSLzbmea2SxgHvDS2MsWEZFYnbWPPphh724ic2anAt939y1mdg9Q5+6PAXcHD2vuAY4TeWoOQbuHgK1EpmX9zJlG3IiIyPiLu0nNNLxSRGT0xjq8clJoae/mn3+1k60HW8/eWEQkicR0Z+xkYGb8y1M7ae/pZeH0grDLERGJGwlzRl+Ync5Vc6ayZvNh4q07SkQkTAkT9AC11eXsPdbOG0fawi5FRCRuJFTQr1hYhhk8sflw2KWIiMSNhAr60oIsllQVs2aLgl5EZEBCBT3Ayupyth5qZX9ze9iliIjEhYQL+trqcgCd1YuIBBIu6Kum5rCgPF9BLyISSLigB1i5qJy6N4/TdLIr7FJEREKXkEFfW12OO6zdeiTsUkREQpeQQb+gPJ+ZU3PUfSMiQoIGvZlRW13O87uO0trZE3Y5IiKhSsigB6itLqOnz1m3vTHsUkREQpWwQb+4spiS/EzdJSsiSS9hgz4lxVixsIyndzTR2aNnnYhI8krYoIfIMMuOnj6e3Xk07FJEREKT0EF/5eypFGSlqftGRJJaQgd9emoKN1xcxq+3H6Gnrz/sckREQpHQQQ+worqclvYeXtrTHHYpIiKhSPigv2Z+CVnpKbp5SkSSVsIHfXZGKtfML+HJLUfo79cjBkUk+SR80ENk7pvDrZ1samgJuxQRkfMuKYL++gVlpKUYa7ZokjMRST5JEfSFOelcNWcqa7Ycxl3dNyKSXJIi6CEy+mbP0VPsbGwLuxQRkfMqaYK+dmEZZrBGN0+JSJJJmqAvLchicWURT2iYpYgkmZiC3sxWmtkOM6s3sy+MsP3zZrbVzF4zs1+b2cyobX1m9mrwemw8ix+tlYvK2XKwlf3N7WGWISJyXp016M0sFbgXeBewELjdzBYOa/YKUOPubwMeAb4Wta3D3S8LXjeNU93npLa6HEA3T4lIUonljH4ZUO/uu929G1gN3BzdwN3XufvAafJ6YMb4ljk+Zk7NZUF5Pk9qmKWIJJFYgr4C2B+13BCsO51PAL+MWs4yszozW29m7xtpBzO7M2hT19TUFENJ5662upwNbzbTdLJrQn+PiEi8iCXobYR1Iw5GN7OPADXA16NWV7l7DfAh4J/MbM5bPsz9PnevcfeakpKSGEo6d7XV5bjDr7bprF5EkkMsQd8AVEYtzwAODm9kZjcAfwnc5O6Dp8vufjD4uRt4Glg8hnrH7OIL8qmakqN+ehFJGrEE/QZgnpnNMrMMYBUwZPSMmS0GvkMk5Buj1hebWWbwfhrwdmDreBV/LsyM2uoyflt/lNbOnjBLERE5L84a9O7eC9wNrAG2AQ+5+xYzu8fMBkbRfB3IAx4eNozyYqDOzDYB64CvunuoQQ+R7puePmfd9sazNxYRmeTSYmnk7o8Djw9b91dR7284zX7PA5eMpcCJsKSqmJL8TJ7ccoSbLzvT98oiIpNf0twZGy0lxbhxYRnrdjTS2dMXdjkiIhMqKYMeYGV1Oe3dfTy382jYpYiITKikDforZ08lPytNc9+ISMJL2qDPSEvh+gWl/HrbEXr7+sMuR0RkwiRt0ENkkrPj7T28tLc57FJERCZMUgf98vklZKalaI56EUloSR30ORlpXDO/hDVbjtDfr0cMikhiSuqgh8jNU4dbO3ntwImwSxERmRBJH/TXX1xKaopp7hsRSVhJH/RFORlcNXsqazYfxl3dNyKSeJI+6AFqq8vYffQU9Y1tYZciIjLuFPTACj1iUEQSmIIeKCvIYnFVke6SFZGEpKAPrKwuZ/OBVhqOt5+9sYjIJKKgD9QG3Td6cLiIJBoFfeDCablcVJav7hsRSTgK+ii1i8qp29vM0bauszcWEZkkFPRRaqvL6Hf41VZ134hI4lDQR1l4QQGVU7I1zFJEEoqCPoqZUbuwnN/WH+NkZ0/Y5YiIjAsF/TC1i8rp7utn3Y6msEsRERkXCvphllQVMy0vU903IpIwFPTDpKYYNy4s4+ntjXT29IVdjojImCnoR7ByUTmnuvv4bf3RsEsRERkzBf0Irpo9lfysNHXfiEhCUNCPICMthesWlLJ26xF6+/rDLkdEZEwU9Kexsrqc4+09bNh7POxSRETGREF/GtdcVEJmWoq6b0Rk0osp6M1spZntMLN6M/vCCNs/b2Zbzew1M/u1mc2M2naHme0MXneMZ/ETKScjjeXzS3hyix4xKCKT21mD3sxSgXuBdwELgdvNbOGwZq8ANe7+NuAR4GvBvlOALwNXAMuAL5tZ8fiVP7Fqq8s5eKKT1w+cCLsUEZFzFssZ/TKg3t13u3s3sBq4ObqBu69z94EndqwHZgTva4G17t7s7seBtcDK8Sl94t1wcSmpKcYTm9V9IyKTVyxBXwHsj1puCNadzieAX45mXzO708zqzKyuqSl+ph4oysngytlT1E8vIpNaLEFvI6wbsdPazD4C1ABfH82+7n6fu9e4e01JSUkMJZ0/tdXl7Go6RX3jybBLERE5J7EEfQNQGbU8Azg4vJGZ3QD8JXCTu3eNZt94tmJh5BGDa/SIQRGZpGIJ+g3APDObZWYZwCrgsegGZrYY+A6RkG+M2rQGWGFmxcGXsCuCdZNGeWEWl1UWqftGRCatswa9u/cCdxMJ6G3AQ+6+xczuMbObgmZfB/KAh83sVTN7LNi3GfhbIgeLDcA9wbpJpba6nNcaTnCgpSPsUkRERs3ibYx4TU2N19XVhV3GELub2rjum8/w5d9fyMffPivsckRE3sLMNrp7zUjbdGdsDGaX5DG/LE/DLEVkUlLQx2hldTkb9jZzrK3r7I1FROKIgj5GK6rL6Xf49bbGszcWEYkjCvoYVU8voKIomyc0+kZEJhkFfYzMjJWLynlu51HaunrDLkdEJGYK+lGorS6nu6+fddvVfSMik4eCfhQun1nMtLwM3TwlIpOKgn4UUlOMGxeWsW57I509fWGXIyISEwX9KNVWl3Oqu4/ndx0NuxQRkZgo6Efp6jnTyM9MY81mTXImIpODgn6UMtJSuHZBKWu3HaG3rz/sckREzkpBfw5WLiqn+VQ3dW8eD7sUEZGzUtCfg2vml5CRlqLRNyIyKSjoz0FuZhrL55Xw5JYjxNvsnyIiwynoz1FtdRkHWjrYfKA17FJERM5IQX+Obri4jNQU44kth8IuRUTkjBT056g4N4MrZk3Rs2RFJO4p6Megtrqc+sY26hvbwi5FROS0FPRjsKK6DECjb0Qkrinox+CCwmwurSziSQW9iMQxBf0Y1VaXsanhBAdbOsIuRURkRAr6MVpZXQ6gs3oRiVsK+jGaXZLHvNI8jb4RkbiloB8HKxeV8+KeYzSf6g67FBGRt1DQj4Pa6nL6HX61TWf1IhJ/FPTjoHp6ARVF2azZrH56EYk/CvpxYGbUVpfzbP1R2rp6wy5HRGQIBf04qa0uo7u3n2d2NIVdiojIEDEFvZmtNLMdZlZvZl8YYftyM3vZzHrN7JZh2/rM7NXg9dh4FR5vai6cwtTcDJ7QMEsRiTNpZ2tgZqnAvcCNQAOwwcwec/etUc32AR8D/scIH9Hh7peNQ61xLTXFuHFhGT9/7RBdvX1kpqWGXZKICBDbGf0yoN7dd7t7N7AauDm6gbvvdffXgKR+iGptdTltXb08X38s7FJERAbFEvQVwP6o5YZgXayyzKzOzNab2ftGamBmdwZt6pqaJm8f99Vzp5KXmaZJzkQkrsQS9DbCutE8P6/K3WuADwH/ZGZz3vJh7ve5e42715SUlIzio+NLZloq1y4oZe3WI/T16xGDIhIfYgn6BqAyankGcDDWX+DuB4Ofu4GngcWjqG/SWVldzrFT3dTtbQ67FBERILag3wDMM7NZZpYBrAJiGj1jZsVmlhm8nwa8Hdh65r0mt3deVEJGWormvhGRuHHWoHf3XuBuYA2wDXjI3beY2T1mdhOAmS01swbgVuA7ZrYl2P1ioM7MNgHrgK8OG62TcHIz0/i9udNYs+Uw7uq+EZHwnXV4JYC7Pw48PmzdX0W930CkS2f4fs8Dl4yxxkmndlE5v97eyJaDrSyqKAy7HBFJcrozdgLccHEZKaZHDIpIfFDQT4ApuRlcMWsqT2iSMxGJAwr6CVJbXcbOxjZ2NbWFXYqIJDkF/QRZETxiUN03IhI2Bf0EmV6UzaUzCjXMUkRCp6CfQCuqy9m0v4VDJzrCLkVEkpiCfgKtXBTpvnlSZ/UiEiIF/QSaU5LH3NI89dOLSKgU9BNsZXU5L+5p5vip7rBLEZEkpaCfYLXV5fT1Oz9a/2bYpYhIkoppCgQ5d4sqClixsIxvrn0DgLuvm4vZSDM/i4hMDJ3RTzAz494PL+EPllTwzbVvcM/Pt9KvuepF5DzSGf15kJ6awjduuZTinAzuf24PLe09fO2Wt5GequOsiEw8Bf15kpJifOk9FzMlN4Ovr9lBS3s3//bhy8nO0EPERWRi6ZTyPDIzPnPtXL7y/kt4+o0mPnr/i5xo7wm7LBFJcAr6EHzoiiru/dASXms4wW33vUBja2fYJYlIAlPQh+Tdl1zA9z+2lH3N7Xzg28/z5rFTYZckIglKQR+id8ybxgOfvJK2zl4+8O8vsPVga9gliUgCUtCH7NLKIh6+62rSU43b7nuBl/Y0h12SiCQYBX0cmFuax6OfvprS/Ew+ev+L/GqrJkETkfGjoI8T04uyefiuq1lQns+nfrSRRzc2hF2SiCQIBX0cmZKbwY8/eSVXzp7Cnz28ie89uzvskkQkASjo40xeZhrf/9hS3rWonL/7xTa+vmY77poyQUTOnYI+DmWmpfKvH1rC7cuquHfdLv7iZ5vp0/w4InKONAVCnEpNMb7y/kVMyU3n3nW7ONHRzT/edhmZaZoyQURGR0Efx8yMP69dQHFOBn/3i22c6NjAdz5aQ16m/rOJSOzUdTMJ/NHvzeabt17K+t3NfPi762nW06pEZBQU9JPEBy6fwXc+cjnbD5/k1m8/z4GWjrBLEpFJQkE/idywsIwffuIKGlu7uOXfn6e+8WTYJYnIJBBT0JvZSjPbYWb1ZvaFEbYvN7OXzazXzG4Ztu0OM9sZvO4Yr8KT1bJZU1j9qSvp6XNu/fYLbNrfEnZJIhLnzhr0ZpYK3Au8C1gI3G5mC4c12wd8DPjJsH2nAF8GrgCWAV82s+Kxl53cqqcX8uinryIvK43bv7ue53YeDbskEYljsZzRLwPq3X23u3cDq4Gboxu4+153fw3oH7ZvLbDW3Zvd/TiwFlg5DnUnvZlTc3n0rqupmpLDf/uPDTz++qGwSxKROBVL0FcA+6OWG4J1sYhpXzO708zqzKyuqakpxo+W0oIsHrzzKi6ZUchnfvIyP3lxX9gliUgciiXobYR1sd6mGdO+7n6fu9e4e01JSUmMHy0AhTnp/OgTV3DN/BL+4mevc++6ek2ZICJDxBL0DUBl1PIM4GCMnz+WfSVG2RmpfPcPa3jfZdP5+pod/N0vttGvKRNEJBDLLZYbgHlmNgs4AKwCPhTj568BvhL1BewK4IujrlLOKj01hW998DKKcjK4/7k9HD/VzT/c8jbSUzWCViTZnTXo3b3XzO4mEtqpwPfdfYuZ3QPUuftjZrYU+BlQDPy+mf2Nu1e7e7OZ/S2RgwXAPe6uRyhNkJQU48u/v5ApuRl8a+0bnOjo4d4PLyErXfPjiCQzi7f+3JqaGq+rqwu7jEnvh+vf5K/+azNLZ07hu3fUUJidHnZJIjKBzGyju9eMtE3X9Qnqo1fO5F9uX8wr+4+z6r71NJ7sDLskEQmJgj6Bvfdt07n/jqXsPXqKW7/9AvuOtYddkoiEQEGf4JbPL+HHn7yCEx09fODbz7PtUGvYJYnIeaagTwJLqop5+FNXkWrGbd95gbq9+j5cJJko6JPEvLJ8Hvn0VUzLy+Qj97/IU9uPhF2SiJwnCvokMqM4h4fuuoq5pXl88gcb+dkrDWGXJCLngYI+yUzLy+SBT17J0guL+dyDm/jzhzfxyr7jmjZBJIHp4aNJKD8rnf/4+DK+8vg2HtnYwMMbG7ioLJ9Vyyp5/+IKinIywi5RRMaRbphKcic7e/j5a4dY/dI+NjWcICMthZXV5axaVsmVs6aSkjLSvHQiEm/OdMOUgl4GbT3YyoMb9vGzVw7Q2tnLzKk5fLCmklsvn0FpQVbY5YnIGSjoZVQ6e/p4YvNhHnhpHy/uaSY1xbhuQSm3L6tk+bwS0jRRmkjcOVPQq49e3iIrPZX3La7gfYsr2N3UxoN1+3l0YwNrtx6hvCCLD9bM4NaaSiqn5IRdqojEQGf0EpOevn5+ve0Iqzfs55k3Ik8Be8fcaaxaWsWNC8vISNNZvkiY1HUj4+pASwcP1+3noQ37OXiikym5GXxgSQW3La1kbml+2OWJJCUFvUyIvn7n2Z1NPLhhP2u3HqG336mZWcyqZVW855ILyM7QPPgi54uCXiZc08kufvpyAw9u2M/uo6fIz0zj5sXTWbW0ikUVhWGXJ5LwFPRy3rg7L+1p5sEN+/nF64fo6u1nUUUBty2t4ubLplOQpQegiEwEBb2E4kR7D/+16QAPvLSfbYdayUpP4T2XTGfVskpqZhZjppuxRMaLgl5C5e68fuAEqzfs57FXD9LW1cucklxWLa3iD5ZUMDUvM+wSRSY9Bb3EjVNdvfzi9ciUCy/vayE91VixsJzbllbyjrnTNOWCyDlS0EtceuPISVa/tJ+fvtJAS3sPFUXZ3La0kltrZnBBYXbY5YlMKgp6iWtdvX08ueUIqzfs47f1x0gxWHrhFK5bUMr1F5cypyRP/fkiZ6Ggl0lj37F2Ht4YGZe//fBJACqnZHPdRaVcu6CUK2dPJStd4/NFhlPQy6R0oKWDddsbWbe9kd/uOkpnTz/Z6am8fe5Url1QynULStXFIxJQ0Muk19nTxwu7jvHU9kae2t7IgZYOABaU5w928VxWWUyqvsyVJKWgl4Ti7uxsbBsM/Y1vHqev3ynOSeea+SVcu6CUa+aX6ElZklQU9JLQTrT38JudTazb3sjTbzTRfKqbFIPLZxYPdvFcVJavL3QloSnoJWn09Tuv7m9hXXC2v/VQKwAVRdlcu6CE6xaUctXsaZpwTRLOmIPezFYC/wykAt9z968O254J/AC4HDgG3Obue83sQmAbsCNout7d7zrT71LQy3g6fKKTdTsiof/b+qO0d/eRmZbC1XOmct2CyEieGcV6gIpMfmMKejNLBd4AbgQagA3A7e6+NarNHwNvc/e7zGwV8H53vy0I+p+7+6JYi1XQy0Tp6u3jxd3Ng337+5rbAZhflse1C0q5fkEZS6qK9KhEmZTGGvRXAX/t7rXB8hcB3P3vo9qsCdq8YGZpwGGgBJiJgl7ikLuzq+nUYBfPhr3N9PY7hdnpLJ9fwnULSrhmfilTcvWFrkwOY31mbAWwP2q5AbjidG3cvdfMTgBTg22zzOwVoBX4krs/O0KBdwJ3AlRVVcVQksjYmBlzS/OYW5rHJ5fPprWzh+d2HuWp7Y08vaOR/7fpIGawuLJosItn4QUF+kJXJqVYgn6kf9nDLwNO1+YQUOXux8zscuD/mlm1u7cOaeh+H3AfRM7oY6hJZFwVZKXz7ksu4N2XXEB/f2S2zae2N7JuRyPfePINvvHkG5QXZHH5zGLmlOQyJzhIzJ6Wpy92Je7FEvQNQGXU8gzg4GnaNARdN4VAs0f6hboA3H2jme0C5gPqm5G4lZJiXFpZxKWVRXzuxvk0nuzk6R1NPL2jkc0HT/DLzYfoD05HzCIjeuaW5jGnJG/wKmFOSZ66fSRuxBL0G4B5ZjYLOACsAj40rM1jwB3AC8AtwFPu7mZWQiTw+8xsNjAP2D1u1YucB6X5WXywppIP1kTOdzp7+th77BT1jW3sajxFfVMb9Y1tvLDrGF29/YP7TcnNYE5J7mDwzynNY25JHhVF2ZqOWc6rswZ90Od+N7CGyPDK77v7FjO7B6hz98eA+4Efmlk90EzkYACwHLjHzHqBPuAud2+eiD+IyPmSlZ7KgvICFpQXDFnf3+8caOmIHACC8K9vbOOXmw/T0t4TtX8Ks6flveUq4MJpOWSmqRtIxp9umBI5D461dbGr6dRg+A8cCAbm7AFIMaiakjMY/nOiDgSF2XrWrpzZWEfdiMgYTc3LZGpeJstmTRmyvqO7j11NkeDf1dg22A307M6jdPf9rhuoJD9zSDfQwFVAeUGWRgLJWSnoRUKUnZHKoopCFlUUDlnf29fP/uMdQ8J/V1Mb//XqQU529g62y81IZU5pHjOn5jK9KIuKomwqirKZHrx0JSCgoBeJS2mpKcyalsusabncQNngenen6WQX9cEVwEB30GsNLazZ3DnkKgAgPzON6UXZVBRnM70oK/J+4FWcTWl+lqZ2TgIKepFJxMwoLciitCCLq+dMG7Ktv9852tbFgZYODrR0cLClg4MtnTQcj7zf+OZxTnT0DNknNcUoL8iionjgSiCLiqIcphdlMaM4clWQk6GYmOz0X1AkQaSk/O4gsLiqeMQ2bV29HGrpoGHwQNDBgeORA8JLe5o53NpJX//QARpFOemD3UHRXUMDVwnTcjM1XDTOKehFkkheZhrzyvKZV5Y/4vbevn4aT3YNXhEcGDwQdLDvWDsv7DpGW1fvkH0y0lKYXpg1+L1AdNdQWUEWJfmZFGSl6UvjECnoRWRQWmrKYGCPxN1p7ewdDP+DJyIHgoEDw7M7m2g82cXwUduZaSmU5GdSmp9JSfAqzc8asq40P4upeRmka/bQcaegF5GYmRmF2ekUZqezcHrBiG26e/s50hr5bqDxZCeNrV00tXXR2NpJU1sXe46e4sU9zUNuIos2JTdjyAGhJD+TkrxMSguygp+RdfmZukqIlYJeRMZVRloKlVNyqJxy5ge6dPX2cbStm6aTXTSd7KLxZGfws2tw3e6mUzSd7HrLaCKI3GE8eBAIrg6GXyGU5GfqKgEFvYiEJDMtdbA//0zcnRMdPW85CEQfGHY1tbF+z7ERrxLMYEpOxpArhGl5mRRmp1OUk05xTgZF2ekU5WQMLmelpyTU1YKCXkTimpkFIZxx2i+RBwxcJTS2Rg4CkS6joT93NbbR3N5NZ89brxIGZKSlUJyTTlF2JPwHDgCFQw4MQw8OhdnpZKXH51xFCnoRSRixXiVAZBbSlvYejrd309LeQ0t7Ny0dkeUT7T2/29bRw56jp3ilvYWW9p4Ru5EGZKen/u4AkJ1OcW46hdkZkYPGkANHZF1hsC4jbWK7lhT0IpKUstJTKS9MpbwwK+Z93J2Onj6ODxwYggNCS8fvDhbHB9a1d/PGkbbBds5Vz8sAAAS/SURBVL39p59AMjcjlaKcDJbMLOZfbl88Hn+8IRT0IiIxMjNyMtLIyUiL6aphgLtzqruP46e6OdEx7CqivSdycOjo5oJRHHRGQ0EvIjLBzIy8zDTyMtOGPK7vfEnuMUciIklAQS8ikuAU9CIiCU5BLyKS4BT0IiIJTkEvIpLgFPQiIglOQS8ikuDMhz8hIGRm1gS8OYaPmAYcHadyxpPqGh3VNTqqa3QSsa6Z7l4y0oa4C/qxMrM6d68Ju47hVNfoqK7RUV2jk2x1qetGRCTBKehFRBJcIgb9fWEXcBqqa3RU1+iortFJqroSro9eRESGSsQzehERiaKgFxFJcAkT9Gb2fTNrNLPNYdcywMwqzWydmW0zsy1m9tmwawIwsywze8nMNgV1/U3YNUUzs1Qze8XMfh52LQPMbK+ZvW5mr5pZXdj1DDCzIjN7xMy2B//Orgq7JgAzuyj4uxp4tZrZn8ZBXZ8L/s1vNrMHzGxiHuk0Smb22aCmLRPx95QwffRmthxoA37g7ovCrgfAzC4ALnD3l80sH9gIvM/dt4ZclwG57t5mZunAc8Bn3X19mHUNMLPPAzVAgbu/N+x6IBL0QI27x9VNNmb2n8Cz7v49M8sActy9Jey6oplZKnAAuMLdx3Iz5FjrqCDyb32hu3eY2UPA4+7+H2HVFNS1CFgNLAO6gSeAT7v7zvH6HQlzRu/uvwGaw64jmrsfcveXg/cngW1ARbhVgUe0BYvpwSsujvhmNgN4D/C9sGuJd2ZWACwH7gdw9+54C/nA9cCuMEM+ShqQbWZpQA5wMOR6AC4G1rt7u7v3As8A7x/PX5AwQR/vzOxCYDHwYriVRATdI68CjcBad4+LuoB/Av4n0B92IcM48KSZbTSzO8MuJjAbaAL+T9DV9T0zyw27qBGsAh4Iuwh3PwB8A9gHHAJOuPuT4VYFwGZguZlNNbMc4N0wvo+WVdCfB2aWBzwK/Km7t4ZdD4C797n7ZcAMYFlw+RgqM3sv0OjuG8OuZQRvd/clwLuAzwRdhWFLA5YA/+7ui4FTwBfCLWmooDvpJuDhOKilGLgZmAVMB3LN7CPhVgXuvg34B2AtkW6bTUDveP4OBf0EC/rAHwV+7O4/Dbue4YJL/aeBlSGXAvB24KagP3w1cJ2Z/SjckiLc/WDwsxH4GZH+1LA1AA1RV2OPEAn+ePIu4GV3PxJ2IcANwB53b3L3HuCnwNUh1wSAu9/v7kvcfTmRLuhx658HBf2ECr70vB/Y5u7fCrueAWZWYmZFwftsIv8DbA+3KnD3L7r7DHe/kMjl/lPuHvoZl5nlBl+mE3SNrCByuR0qdz8M7Dezi4JV1wOhftE/gtuJg26bwD7gSjPLCf7fvJ7I92ahM7PS4GcV8AeM899Z2nh+WJjM7AHgncA0M2sAvuzu94dbFW8HPgq8HvSHA/yFuz8eYk0AFwD/GYyGSAEecve4GcoYh8qAn0WygTTgJ+7+RLglDfoT4MdBF8lu4OMh1zMo6G++EfhU2LUAuPuLZvYI8DKRrpFXiJ+pEB41s6lAD/AZdz8+nh+eMMMrRURkZOq6ERFJcAp6EZEEp6AXEUlwCnoRkQSnoBcRSXAKehGRBKegFxFJcP8fkGhih2INQVgAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<Figure size 432x288 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "from sklearn.cluster import KMeans\n",
    "\n",
    "loss = []\n",
    "\n",
    "for i in range(1, 10):\n",
    "    kmeans = KMeans(n_clusters=i, max_iter=100).fit(data)\n",
    "    loss.append(kmeans.inertia_ / len(data) / 3)\n",
    "\n",
    "plt.title('K with loss')\n",
    "plt.plot(range(1, 10), loss)\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "colab": {
   "collapsed_sections": [],
   "name": "Clustering.ipynb",
   "provenance": [],
   "version": "0.3.2"
  },
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
